### comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/voterank_alg.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Algorithm to select influential nodes in a graph using VoteRank."""
2
3 __all__ = ["voterank"]
4
5
6 def voterank(G, number_of_nodes=None):
7 """Select a list of influential nodes in a graph using VoteRank algorithm
8
9 VoteRank _ computes a ranking of the nodes in a graph G based on a
10 voting scheme. With VoteRank, all nodes vote for each of its in-neighbours
11 and the node with the highest votes is elected iteratively. The voting
12 ability of out-neighbors of elected nodes is decreased in subsequent turns.
13
14 Note: We treat each edge independently in case of multigraphs.
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 References
31 ----------
32 ..  Zhang, J.-X. et al. (2016).
33 Identifying a set of influential spreaders in complex networks.
34 Sci. Rep. 6, 27823; doi: 10.1038/srep27823.
35 """
36 influential_nodes = []
37 voterank = {}
38 if len(G) == 0:
39 return influential_nodes
40 if number_of_nodes is None or number_of_nodes > len(G):
41 number_of_nodes = len(G)
42 if G.is_directed():
43 # For directed graphs compute average out-degree
44 avgDegree = sum(deg for _, deg in G.out_degree()) / len(G)
45 else:
46 # For undirected graphs compute average degree
47 avgDegree = sum(deg for _, deg in G.degree()) / len(G)
48 # step 1 - initiate all nodes to (0,1) (score, voting ability)
49 for n in G.nodes():
50 voterank[n] = [0, 1]
51 # Repeat steps 1b to 4 until num_seeds are elected.
52 for _ in range(number_of_nodes):
53 # step 1b - reset rank
54 for n in G.nodes():
55 voterank[n] = 0
56 # step 2 - vote
57 for n, nbr in G.edges():
58 # In directed graphs nodes only vote for their in-neighbors
59 voterank[n] += voterank[nbr]
60 if not G.is_directed():
61 voterank[nbr] += voterank[n]
62 for n in influential_nodes:
63 voterank[n] = 0
64 # step 3 - select top node
65 n = max(G.nodes, key=lambda x: voterank[x])
66 if voterank[n] == 0:
67 return influential_nodes
68 influential_nodes.append(n)
69 # weaken the selected node
70 voterank[n] = [0, 0]
71 # step 4 - update voterank properties
72 for _, nbr in G.edges(n):
73 voterank[nbr] -= 1 / avgDegree
74 voterank[nbr] = max(voterank[nbr], 0)
75 return influential_nodes