Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/voterank_alg.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 [1]_ 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 .. [1] 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] = 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][0] += voterank[nbr][1] | |
60 if not G.is_directed(): | |
61 voterank[nbr][0] += voterank[n][1] | |
62 for n in influential_nodes: | |
63 voterank[n][0] = 0 | |
64 # step 3 - select top node | |
65 n = max(G.nodes, key=lambda x: voterank[x][0]) | |
66 if voterank[n][0] == 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] -= 1 / avgDegree | |
74 voterank[nbr][1] = max(voterank[nbr][1], 0) | |
75 return influential_nodes |