Coverage for src/driada/network/graph_utils.py: 52.17%

1import networkx as nx 

2import numpy as np 

3from copy import deepcopy 

4 

5from .randomization import * 

6 

7def get_giant_cc_from_graph(G): 

8 # this function preserves graph type: nx.Graph --> nx.Graph; nx.DiGraph --> nx.DiGraph 

9 connected_components = sorted(nx.connected_components(G), key=len, reverse=True) 

10 # print([len(c) for c in connected_components]) 

11 gcc = connected_components[0] 

12 

13 return nx.subgraph(G, gcc) 

14 

15 

16def get_giant_scc_from_graph(G): 

17 # for a directed graph, its largest strongly connected component is returned. 

18 if nx.is_directed(G): 

19 strongly_connected_components = sorted(nx.strongly_connected_components(G), 

20 key=len, 

21 reverse=True) 

22 

23 gcc = strongly_connected_components[0] 

24 

25 else: 

26 raise ValueError('Strongly connected components are meaningless for undirected graphs') 

27 

28 return nx.subgraph(G, gcc) 

29 

30 

31def remove_selfloops_from_graph(graph): 

32 g = deepcopy(graph) # NetworkX graphs are highly nested, deepcopy is safer 

33 # this function preserves graph type: nx.Graph --> nx.Graph; nx.DiGraph --> nx.DiGraph 

34 g.remove_edges_from(list(nx.selfloop_edges(g))) 

35 return g 

36 

37 

38def remove_isolates_and_selfloops_from_graph(graph): 

39 g = deepcopy(graph) # NetworkX graphs are highly nested, deepcopy is safer 

40 # this function preserves graph type: nx.Graph --> nx.Graph; nx.DiGraph --> nx.DiGraph 

41 g.remove_nodes_from(list(nx.isolates(g))) 

42 g.remove_edges_from(list(nx.selfloop_edges(g))) 

43 return g 

44 

45 

46def remove_isolates_from_graph(graph): 

47 g = deepcopy(graph) # NetworkX graphs are highly nested, deepcopy is safer 

48 g.remove_nodes_from(list(nx.isolates(g))) 

49 return g 

50 

51 

52def small_world_index(G, nrand=10, null_model='erdos-renyi'): 

53 asp = nx.average_shortest_path_length(G) 

54 acc = nx.average_clustering(G) 

55 

56 r_asp_list = [] 

57 r_acc_list = [] 

58 i = 0 

59 while i < nrand: 

60 if null_model == 'maslov-sneppen': 

61 #ar = adj_random_rewiring_iom_preserving(sp.csr_array(data), is_weighted=True).todense() 

62 raise Exception('not implemented yet') 

63 

64 elif null_model == 'erdos-renyi': 

65 n = G.number_of_nodes() 

66 p = 2.0 * G.number_of_edges() / n / (n - 1) 

67 Gr = nx.gnp_random_graph(n, p) 

68 

69 if nx.is_connected(Gr): 

70 i += 1 

71 r_asp_list.append(nx.average_shortest_path_length(Gr)) 

72 r_acc_list.append(nx.average_clustering(Gr)) 

73 

74 sw = (acc / np.mean(r_acc_list)) / (asp / np.mean(r_asp_list)) 

75 return sw