Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Algorithm to select influential nodes in a graph using VoteRank."""
3import networkx as nx
5__all__ = ["voterank"]
8@nx._dispatchable
9def voterank(G, number_of_nodes=None):
10 """Select a list of influential nodes in a graph using VoteRank algorithm
12 VoteRank [1]_ computes a ranking of the nodes in a graph G based on a
13 voting scheme. With VoteRank, all nodes vote for each of its in-neighbors
14 and the node with the highest votes is elected iteratively. The voting
15 ability of out-neighbors of elected nodes is decreased in subsequent turns.
17 Parameters
18 ----------
19 G : graph
20 A NetworkX graph.
22 number_of_nodes : integer, optional
23 Number of ranked nodes to extract (default all nodes).
25 Returns
26 -------
27 voterank : list
28 Ordered list of computed seeds.
29 Only nodes with positive number of votes are returned.
31 Examples
32 --------
33 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 4)])
34 >>> nx.voterank(G)
35 [0, 1]
37 The algorithm can be used both for undirected and directed graphs.
38 However, the directed version is different in two ways:
39 (i) nodes only vote for their in-neighbors and
40 (ii) only the voting ability of elected node and its out-neighbors are updated:
42 >>> G = nx.DiGraph([(0, 1), (2, 1), (2, 3), (3, 4)])
43 >>> nx.voterank(G)
44 [2, 3]
46 Notes
47 -----
48 Each edge is treated independently in case of multigraphs.
50 References
51 ----------
52 .. [1] Zhang, J.-X. et al. (2016).
53 Identifying a set of influential spreaders in complex networks.
54 Sci. Rep. 6, 27823; doi: 10.1038/srep27823.
55 """
56 influential_nodes = []
57 vote_rank = {}
58 if len(G) == 0:
59 return influential_nodes
60 if number_of_nodes is None or number_of_nodes > len(G):
61 number_of_nodes = len(G)
62 if G.is_directed():
63 # For directed graphs compute average out-degree
64 avgDegree = sum(deg for _, deg in G.out_degree()) / len(G)
65 else:
66 # For undirected graphs compute average degree
67 avgDegree = sum(deg for _, deg in G.degree()) / len(G)
68 # step 1 - initiate all nodes to (0,1) (score, voting ability)
69 for n in G.nodes():
70 vote_rank[n] = [0, 1]
71 # Repeat steps 1b to 4 until num_seeds are elected.
72 for _ in range(number_of_nodes):
73 # step 1b - reset rank
74 for n in G.nodes():
75 vote_rank[n][0] = 0
76 # step 2 - vote
77 for n, nbr in G.edges():
78 # In directed graphs nodes only vote for their in-neighbors
79 vote_rank[n][0] += vote_rank[nbr][1]
80 if not G.is_directed():
81 vote_rank[nbr][0] += vote_rank[n][1]
82 for n in influential_nodes:
83 vote_rank[n][0] = 0
84 # step 3 - select top node
85 n = max(G.nodes, key=lambda x: vote_rank[x][0])
86 if vote_rank[n][0] == 0:
87 return influential_nodes
88 influential_nodes.append(n)
89 # weaken the selected node
90 vote_rank[n] = [0, 0]
91 # step 4 - update voterank properties
92 for _, nbr in G.edges(n):
93 vote_rank[nbr][1] -= 1 / avgDegree
94 vote_rank[nbr][1] = max(vote_rank[nbr][1], 0)
95 return influential_nodes