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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """Algorithm to select influential nodes in a graph using VoteRank."""
shellac
parents:
diff changeset
2
shellac
parents:
diff changeset
3 __all__ = ["voterank"]
shellac
parents:
diff changeset
4
shellac
parents:
diff changeset
5
shellac
parents:
diff changeset
6 def voterank(G, number_of_nodes=None):
shellac
parents:
diff changeset
7 """Select a list of influential nodes in a graph using VoteRank algorithm
shellac
parents:
diff changeset
8
shellac
parents:
diff changeset
9 VoteRank [1]_ computes a ranking of the nodes in a graph G based on a
shellac
parents:
diff changeset
10 voting scheme. With VoteRank, all nodes vote for each of its in-neighbours
shellac
parents:
diff changeset
11 and the node with the highest votes is elected iteratively. The voting
shellac
parents:
diff changeset
12 ability of out-neighbors of elected nodes is decreased in subsequent turns.
shellac
parents:
diff changeset
13
shellac
parents:
diff changeset
14 Note: We treat each edge independently in case of multigraphs.
shellac
parents:
diff changeset
15
shellac
parents:
diff changeset
16 Parameters
shellac
parents:
diff changeset
17 ----------
shellac
parents:
diff changeset
18 G : graph
shellac
parents:
diff changeset
19 A NetworkX graph.
shellac
parents:
diff changeset
20
shellac
parents:
diff changeset
21 number_of_nodes : integer, optional
shellac
parents:
diff changeset
22 Number of ranked nodes to extract (default all nodes).
shellac
parents:
diff changeset
23
shellac
parents:
diff changeset
24 Returns
shellac
parents:
diff changeset
25 -------
shellac
parents:
diff changeset
26 voterank : list
shellac
parents:
diff changeset
27 Ordered list of computed seeds.
shellac
parents:
diff changeset
28 Only nodes with positive number of votes are returned.
shellac
parents:
diff changeset
29
shellac
parents:
diff changeset
30 References
shellac
parents:
diff changeset
31 ----------
shellac
parents:
diff changeset
32 .. [1] Zhang, J.-X. et al. (2016).
shellac
parents:
diff changeset
33 Identifying a set of influential spreaders in complex networks.
shellac
parents:
diff changeset
34 Sci. Rep. 6, 27823; doi: 10.1038/srep27823.
shellac
parents:
diff changeset
35 """
shellac
parents:
diff changeset
36 influential_nodes = []
shellac
parents:
diff changeset
37 voterank = {}
shellac
parents:
diff changeset
38 if len(G) == 0:
shellac
parents:
diff changeset
39 return influential_nodes
shellac
parents:
diff changeset
40 if number_of_nodes is None or number_of_nodes > len(G):
shellac
parents:
diff changeset
41 number_of_nodes = len(G)
shellac
parents:
diff changeset
42 if G.is_directed():
shellac
parents:
diff changeset
43 # For directed graphs compute average out-degree
shellac
parents:
diff changeset
44 avgDegree = sum(deg for _, deg in G.out_degree()) / len(G)
shellac
parents:
diff changeset
45 else:
shellac
parents:
diff changeset
46 # For undirected graphs compute average degree
shellac
parents:
diff changeset
47 avgDegree = sum(deg for _, deg in G.degree()) / len(G)
shellac
parents:
diff changeset
48 # step 1 - initiate all nodes to (0,1) (score, voting ability)
shellac
parents:
diff changeset
49 for n in G.nodes():
shellac
parents:
diff changeset
50 voterank[n] = [0, 1]
shellac
parents:
diff changeset
51 # Repeat steps 1b to 4 until num_seeds are elected.
shellac
parents:
diff changeset
52 for _ in range(number_of_nodes):
shellac
parents:
diff changeset
53 # step 1b - reset rank
shellac
parents:
diff changeset
54 for n in G.nodes():
shellac
parents:
diff changeset
55 voterank[n][0] = 0
shellac
parents:
diff changeset
56 # step 2 - vote
shellac
parents:
diff changeset
57 for n, nbr in G.edges():
shellac
parents:
diff changeset
58 # In directed graphs nodes only vote for their in-neighbors
shellac
parents:
diff changeset
59 voterank[n][0] += voterank[nbr][1]
shellac
parents:
diff changeset
60 if not G.is_directed():
shellac
parents:
diff changeset
61 voterank[nbr][0] += voterank[n][1]
shellac
parents:
diff changeset
62 for n in influential_nodes:
shellac
parents:
diff changeset
63 voterank[n][0] = 0
shellac
parents:
diff changeset
64 # step 3 - select top node
shellac
parents:
diff changeset
65 n = max(G.nodes, key=lambda x: voterank[x][0])
shellac
parents:
diff changeset
66 if voterank[n][0] == 0:
shellac
parents:
diff changeset
67 return influential_nodes
shellac
parents:
diff changeset
68 influential_nodes.append(n)
shellac
parents:
diff changeset
69 # weaken the selected node
shellac
parents:
diff changeset
70 voterank[n] = [0, 0]
shellac
parents:
diff changeset
71 # step 4 - update voterank properties
shellac
parents:
diff changeset
72 for _, nbr in G.edges(n):
shellac
parents:
diff changeset
73 voterank[nbr][1] -= 1 / avgDegree