How can I remove all nodes except the largest components in a graph?

graph-tool
1

Hi,

I have tried to simulate the phenomenen of cascading failures in
interdependent networks. But I can't remove the nodes that don't belong to
the largest component. Is there any simple solution for this task?

Best,
Liu

attachment.html (307 Bytes)

2

Hello Liu,
there is an example code of what you are looking for in the
"label_largest_component" documentation:
http://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.label_largest_component

Best,
Giuseppe

2014-04-29 9:15 GMT+02:00 Liu <boxiliu.hust(a)gmail.com>:

attachment.html (1.38 KB)

3

Thanks for your help. But I was still confused by the graph filter. My aim
is to to remove the nodes that don't belong to largest component of
subnetwork consisted of type A nodes while the corresponding type B nodes
are remained in the graph. I wrote the script like this,

p = 0.02
G = gt.load_graph(File)
pos = G.vertex_properties['pos']
v_type = G.vertex_properties['v_type']
e_type = G.edge_properties['e_type']
exist = G.new_vertex_property('bool')
G.vertex_properties['exsit'] = exist
exist.a = True

for v in G.vertices():
    if v_type[v]:
        if np.random() < p:
            exist[v] =False
            for n in v.all_neighbours():
                if not v_type[n]:
                    exist[n] = False

G.set_vertex_filter(prop=exist)
G.purge_vertices()

pos = G.vertex_properties['pos']
v_type = G.vertex_properties['v_type']
exist = G.vertex_properties['tag']

gt.graph_draw(G, pos=pos)
# step 1 largest component in network A
UA = gt.GraphView(G, vfilt=v_type)

LCA = gt.label_largest_component(UA)
exist.a = False
for v in G.vertices():
    if LCA[v]:
        exist[v] = True
        for n in v.all_neighbours():
            if not v_type[n]:
                exist[v] = True

G.set_vertex_filter(exist)
line 56: G.purge_vertices()

Console warns that ,
Traceback (most recent call last):
  File "/home/lockheed/PycharmProjects/cascade_failures/MAIN.py", line 56,
in <module>
    G.purge_vertices()
  File "/usr/lib/python2.7/dist-packages/graph_tool/__init__.py", line
1867, in purge_vertices
    new_g = Graph(self, prune=(True, False, False))
  File "/usr/lib/python2.7/dist-packages/graph_tool/__init__.py", line
1133, in __init__
    _prop("v", gv, vorder))
ValueError: Cannot find property map type.

Very appreciate for your help.

best,
Liu
在 2014年4月29日星期二UTC+8下午5时02分02秒，Giuseppe Profiti写道：

attachment.html (5.34 KB)

4

This is a bug in graph-tool. It has been fixed in the most recent git
version.

As a workaround, you can use G.purge_vertices(in_place=True).

Best,
Tiago

5

Dear Tiago,

I used G.purge_vertices(in_place=True). But the vertex filter didn't work.

G.set_vertex_filter(prop=exist)
G.purge_vertices(in_place=True)

gt.graph_draw(G, pos=pos)
# step 1 largest component in network A
UA = gt.GraphView(G, vfilt=v_type)

line 45：LCA = gt.label_largest_component(UA)
exist.a = False
for v in G.vertices():
    if LCA[v]:
        exist[v] = True
        for n in v.all_neighbours():
            if not v_type[n]:
                exist[v] = True

G.set_vertex_filter(exist)
G.purge_vertices(in_place=True)

Console warns that,
Traceback (most recent call last):
  File "/home/lockheed/PycharmProjects/cascade_failures/MAIN.py", line 45,
in <module>
    LCA = gt.label_largest_component(UA)
  File "/usr/lib/python2.7/dist-packages/graph_tool/topology/__init__.py",
line 814, in label_largest_component
    label.a = (c.a == h.argmax()) & (vfilt.a ^ inv)
ValueError: operands could not be broadcast together with shapes (248)
(256)

Thanks for your help!

Best,
Liu

在 2014年4月29日星期二UTC+8下午11时13分06秒，Tiago Peixoto写道：

attachment.html (2.82 KB)

6

This seems to be something else. Could you please provide a full working
example, so I can investigate?

Best,
Tiago

7

I've fixed a related problem in the git version. Please try with
that. If it does not work, please send the full working example, and
I'll check it out.

Best,
Tiago

8

Dear Tiago,

I just send full working example to you. The Network_Prepare.py is to
generate a ER-ER interdependent network as it shows. The MAIN.py is to
simulate the cascading failure in interdependent network.
I will try the newest code on github later. Thank u.

best,
Liu

在 2014年4月30日星期三UTC+8下午3时44分48秒，Tiago Peixoto写道：

attachment.html (2.74 KB)

Network_Prepare.py (2.5 KB)

MAIN.py (1.26 KB)

9

Dear Tiago,

The purge_vertices(in_place = False ) in he newest git version is OK.

Best,
Liu

在 2014年4月30日星期三UTC+8下午3时44分48秒，Tiago Peixoto写道：

attachment.html (2.56 KB)

10

Ok, I tested with in_place = True, and it seems fine as well.

Best,
Tiago