Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def _breake_lcc(self, G, remove_ratio):
- '''
- G:graph
- remove_ratio = ratio for removing high degree nodes
- '''
- #lcc of complete graph
- l = gt.label_largest_component(G)
- lcc_graph = gt.GraphView(G,vfilt=l)
- lcc_org_size = float(lcc_graph.num_vertices())
- lcc_size = [lcc_org_size/lcc_org_size]
- #print 'lcc_size_zero: ', lcc_graph.num_vertices()
- #extract the vertices inside lcc
- node_ind = np.where(l.a==1)[0]
- #compute the degree of all nodes
- degree = lcc_graph.degree_property_map('total')
- #extract the degreee of nodes in the lcc
- lcc_vertex_degree = degree.a[node_ind]
- #sort the nodes based on degree
- sorted_idx = np.argsort(lcc_vertex_degree)[::-1]
- sorted_vertex = set(node_ind[sorted_idx])
- #number of nodes
- n = len(node_ind)
- #number of top x% degree nodes to be removed -ratio to size
- remove_size = int((n*remove_ratio)/100.)
- print 'remove size',remove_size
- step = 1
- #extract top x% vertices to remove
- nodes_to_be_removed = list(sorted_vertex)[:remove_size]
- #removed the above vertices from the list of valid vertices
- valid_vertices = list(sorted_vertex - set(nodes_to_be_removed))
- #continue until there is no other node to remove
- while len(valid_vertices)>0:
- print step * remove_ratio
- # print len(valid_vertices)
- #filter out those nodes from lcc.
- #THIS IS AUTOMATICALLY UPDATE LCC_GRAPH
- l.a[np.array(nodes_to_be_removed)] = False
- #I REALIZED GRAPHVIEW DOES NOT TAKE CARE OF ISOLATED NODE AUTOMATICALLY
- #SO I CHECK FOR THEM MANUALLY
- ind_remove = [int(i) for i in lcc_graph.vertices() if i.out_degree()==0]
- if len(ind_remove)>0:
- print len(ind_remove)
- mask = lcc_graph.new_vertex_property("bool")
- #mask.a[::] = True
- mask.a = l.a.copy()
- #l.a[np.array(ind_remove)] = False
- mask.a[np.array(ind_remove)] = False
- #mask.a[nodes_to_be_removed] = False
- #print np.all(mask.a==l.a)
- lcc_graph = gt.GraphView(lcc_graph, vfilt=mask)
- #update the valid nodes
- valid_vertices = list(set(valid_vertices) - set(ind_remove))
- print len(valid_vertices), len(sorted_vertex),lcc_graph.num_vertices()
- lcc_temp_size = float(lcc_graph.num_vertices())
- #print 'valid', len(valid_vertices),lcc_temp_size
- nodes_to_be_removed = valid_vertices[:int(remove_size)]
- print lcc_temp_size,lcc_org_size
- rel_size = lcc_temp_size/lcc_org_size
- lcc_size.append(rel_size)
- print 'lcc size', rel_size
- print '------------'
- step+=1
- return lcc_size
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement