Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/voterank_alg.py: 12%

1"""Algorithm to select influential nodes in a graph using VoteRank.""" 

2import networkx as nx 

3 

4__all__ = ["voterank"] 

5 

6 

7@nx._dispatch 

8def voterank(G, number_of_nodes=None): 

9 """Select a list of influential nodes in a graph using VoteRank algorithm 

10 

11 VoteRank [1]_ computes a ranking of the nodes in a graph G based on a 

12 voting scheme. With VoteRank, all nodes vote for each of its in-neighbours 

13 and the node with the highest votes is elected iteratively. The voting 

14 ability of out-neighbors of elected nodes is decreased in subsequent turns. 

15 

16 Parameters 

17 ---------- 

18 G : graph 

19 A NetworkX graph. 

20 

21 number_of_nodes : integer, optional 

22 Number of ranked nodes to extract (default all nodes). 

23 

24 Returns 

25 ------- 

26 voterank : list 

27 Ordered list of computed seeds. 

28 Only nodes with positive number of votes are returned. 

29 

30 Examples 

31 -------- 

32 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 4)]) 

33 >>> nx.voterank(G) 

34 [0, 1] 

35 

36 The algorithm can be used both for undirected and directed graphs. 

37 However, the directed version is different in two ways: 

38 (i) nodes only vote for their in-neighbors and 

39 (ii) only the voting ability of elected node and its out-neighbors are updated: 

40 

41 >>> G = nx.DiGraph([(0, 1), (2, 1), (2, 3), (3, 4)]) 

42 >>> nx.voterank(G) 

43 [2, 3] 

44 

45 Notes 

46 ----- 

47 Each edge is treated independently in case of multigraphs. 

48 

49 References 

50 ---------- 

51 .. [1] Zhang, J.-X. et al. (2016). 

52 Identifying a set of influential spreaders in complex networks. 

53 Sci. Rep. 6, 27823; doi: 10.1038/srep27823. 

54 """ 

55 influential_nodes = [] 

56 vote_rank = {} 

57 if len(G) == 0: 

58 return influential_nodes 

59 if number_of_nodes is None or number_of_nodes > len(G): 

60 number_of_nodes = len(G) 

61 if G.is_directed(): 

62 # For directed graphs compute average out-degree 

63 avgDegree = sum(deg for _, deg in G.out_degree()) / len(G) 

64 else: 

65 # For undirected graphs compute average degree 

66 avgDegree = sum(deg for _, deg in G.degree()) / len(G) 

67 # step 1 - initiate all nodes to (0,1) (score, voting ability) 

68 for n in G.nodes(): 

69 vote_rank[n] = [0, 1] 

70 # Repeat steps 1b to 4 until num_seeds are elected. 

71 for _ in range(number_of_nodes): 

72 # step 1b - reset rank 

73 for n in G.nodes(): 

74 vote_rank[n][0] = 0 

75 # step 2 - vote 

76 for n, nbr in G.edges(): 

77 # In directed graphs nodes only vote for their in-neighbors 

78 vote_rank[n][0] += vote_rank[nbr][1] 

79 if not G.is_directed(): 

80 vote_rank[nbr][0] += vote_rank[n][1] 

81 for n in influential_nodes: 

82 vote_rank[n][0] = 0 

83 # step 3 - select top node 

84 n = max(G.nodes, key=lambda x: vote_rank[x][0]) 

85 if vote_rank[n][0] == 0: 

86 return influential_nodes 

87 influential_nodes.append(n) 

88 # weaken the selected node 

89 vote_rank[n] = [0, 0] 

90 # step 4 - update voterank properties 

91 for _, nbr in G.edges(n): 

92 vote_rank[nbr][1] -= 1 / avgDegree 

93 vote_rank[nbr][1] = max(vote_rank[nbr][1], 0) 

94 return influential_nodes