Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / voterank_alg.py @ 5cef0f13

History | View | Annotate | Download (2.77 KB)

1
#   Copyright (C) 2017 by
2
#   Fredrik Erlandsson <fredrik.e@gmail.com>
3
#   All rights reserved.
4
#   BSD license.
5
#
6
"""Algorithm to compute influential seeds in a graph using voterank."""
7
from networkx.utils.decorators import not_implemented_for
8

    
9
__all__ = ['voterank']
10
__author__ = """\n""".join(['Fredrik Erlandsson <fredrik.e@gmail.com>',
11
                            'Piotr Brodka (piotr.brodka@pwr.edu.pl'])
12

    
13

    
14
@not_implemented_for('directed')
15
def voterank(G, number_of_nodes=None, max_iter=10000):
16
    """Compute a list of seeds for the nodes in the graph using VoteRank [1]_.
17

18
    VoteRank computes a ranking of the nodes in the graph G based on a voting
19
    scheme. With VoteRank, all nodes vote for each neighbours and the node with
20
    the highest score is elected iteratively. The voting ability of neighbors of
21
    elected nodes will be decreased in subsequent turn.
22

23
    Parameters
24
    ----------
25
    G : graph
26
        A NetworkX graph.
27

28
    number_of_nodes : integer, optional
29
        Number of ranked nodes to extract (default all nodes).
30

31
    max_iter : integer, optional
32
        Maximum number of iterations to rank nodes.
33

34
    Returns
35
    -------
36
    voterank : list
37
        Ordered list of computed seeds.
38

39
    Raises
40
    ------
41
    NetworkXNotImplemented:
42
        If G is digraph.
43

44
    References
45
    ----------
46
    .. [1] Zhang, J.-X. et al. (2016).
47
        Identifying a set of influential spreaders in complex networks.
48
        Sci. Rep. 6, 27823; doi: 10.1038/srep27823.
49
    """
50
    voterank = []
51
    if len(G) == 0:
52
        return voterank
53
    if number_of_nodes is None or number_of_nodes > len(G):
54
        number_of_nodes = len(G)
55
    avgDegree = sum(deg for _, deg in G.degree()) / float(len(G))
56
    # step 1 - initiate all nodes to (0,1) (score, voting ability)
57
    for _, v in G.nodes(data=True):
58
        v['voterank'] = [0, 1]
59
    # Repeat steps 1b to 4 until num_seeds are elected.
60
    for _ in range(max_iter):
61
        # step 1b - reset rank
62
        for _, v in G.nodes(data=True):
63
            v['voterank'][0] = 0
64
        # step 2 - vote
65
        for n, nbr in G.edges():
66
            G.node[n]['voterank'][0] += G.node[nbr]['voterank'][1]
67
            G.node[nbr]['voterank'][0] += G.node[n]['voterank'][1]
68
        for n in voterank:
69
            G.node[n]['voterank'][0] = 0
70
        # step 3 - select top node
71
        n, value = max(G.nodes(data=True),
72
                       key=lambda x: x[1]['voterank'][0])
73
        if value['voterank'][0] == 0:
74
            return voterank
75
        voterank.append(n)
76
        if len(voterank) >= number_of_nodes:
77
            return voterank
78
        # weaken the selected node
79
        G.node[n]['voterank'] = [0, 0]
80
        # step 4 - update voterank properties
81
        for nbr in G.neighbors(n):
82
            G.node[nbr]['voterank'][1] -= 1 / avgDegree
83
    return voterank