Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / assortativity / connectivity.py @ 5cef0f13

History | View | Annotate | Download (4.46 KB)

1
# -*- coding: utf-8 -*-
2
#
3
#    Copyright (C) 2011 by
4
#    Jordi Torrents <jtorrents@milnou.net>
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
#
10
# Authors: Jordi Torrents <jtorrents@milnou.net>
11
#          Aric Hagberg <hagberg@lanl.gov>
12
from __future__ import division
13

    
14
from collections import defaultdict
15

    
16
import networkx as nx
17

    
18
__all__ = ['average_degree_connectivity',
19
           'k_nearest_neighbors']
20

    
21

    
22
def average_degree_connectivity(G, source="in+out", target="in+out",
23
                                nodes=None, weight=None):
24
    r"""Compute the average degree connectivity of graph.
25

26
    The average degree connectivity is the average nearest neighbor degree of
27
    nodes with degree k. For weighted graphs, an analogous measure can
28
    be computed using the weighted average neighbors degree defined in
29
    [1]_, for a node `i`, as
30

31
    .. math::
32

33
        k_{nn,i}^{w} = \frac{1}{s_i} \sum_{j \in N(i)} w_{ij} k_j
34

35
    where `s_i` is the weighted degree of node `i`,
36
    `w_{ij}` is the weight of the edge that links `i` and `j`,
37
    and `N(i)` are the neighbors of node `i`.
38

39
    Parameters
40
    ----------
41
    G : NetworkX graph
42

43
    source :  "in"|"out"|"in+out" (default:"in+out")
44
       Directed graphs only. Use "in"- or "out"-degree for source node.
45

46
    target : "in"|"out"|"in+out" (default:"in+out"
47
       Directed graphs only. Use "in"- or "out"-degree for target node.
48

49
    nodes : list or iterable (optional)
50
        Compute neighbor connectivity for these nodes. The default is all
51
        nodes.
52

53
    weight : string or None, optional (default=None)
54
       The edge attribute that holds the numerical value used as a weight.
55
       If None, then each edge has weight 1.
56

57
    Returns
58
    -------
59
    d : dict
60
       A dictionary keyed by degree k with the value of average connectivity.
61

62
    Raises
63
    ------
64
    ValueError
65
        If either `source` or `target` are not one of 'in',
66
        'out', or 'in+out'.
67

68
    Examples
69
    --------
70
    >>> G=nx.path_graph(4)
71
    >>> G.edges[1, 2]['weight'] = 3
72
    >>> nx.k_nearest_neighbors(G)
73
    {1: 2.0, 2: 1.5}
74
    >>> nx.k_nearest_neighbors(G, weight='weight')
75
    {1: 2.0, 2: 1.75}
76

77
    See also
78
    --------
79
    neighbors_average_degree
80

81
    Notes
82
    -----
83
    This algorithm is sometimes called "k nearest neighbors" and is also
84
    available as `k_nearest_neighbors`.
85

86
    References
87
    ----------
88
    .. [1] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani,
89
       "The architecture of complex weighted networks".
90
       PNAS 101 (11): 3747–3752 (2004).
91
    """
92
    # First, determine the type of neighbors and the type of degree to use.
93
    if G.is_directed():
94
        if source not in ('in', 'out', 'in+out'):
95
            raise ValueError('source must be one of "in", "out", or "in+out"')
96
        if target not in ('in', 'out', 'in+out'):
97
            raise ValueError('target must be one of "in", "out", or "in+out"')
98
        direction = {'out': G.out_degree,
99
                     'in': G.in_degree,
100
                     'in+out': G.degree}
101
        neighbor_funcs = {'out': G.successors,
102
                          'in': G.predecessors,
103
                          'in+out': G.neighbors}
104
        source_degree = direction[source]
105
        target_degree = direction[target]
106
        neighbors = neighbor_funcs[source]
107
        # `reverse` indicates whether to look at the in-edge when
108
        # computing the weight of an edge.
109
        reverse = (source == 'in')
110
    else:
111
        source_degree = G.degree
112
        target_degree = G.degree
113
        neighbors = G.neighbors
114
        reverse = False
115
    dsum = defaultdict(int)
116
    dnorm = defaultdict(int)
117
    # Check if `source_nodes` is actually a single node in the graph.
118
    source_nodes = source_degree(nodes)
119
    if nodes in G:
120
        source_nodes = [(nodes, source_degree(nodes))]
121
    for n, k in source_nodes:
122
        nbrdeg = target_degree(neighbors(n))
123
        if weight is None:
124
            s = sum(d for n, d in nbrdeg)
125
        else:  # weight nbr degree by weight of (n,nbr) edge
126
            if reverse:
127
                s = sum(G[nbr][n].get(weight, 1) * d for nbr, d in nbrdeg)
128
            else:
129
                s = sum(G[n][nbr].get(weight, 1) * d for nbr, d in nbrdeg)
130
        dnorm[k] += source_degree(n, weight=weight)
131
        dsum[k] += s
132

    
133
    # normalize
134
    dc = {}
135
    for k, avg in dsum.items():
136
        dc[k] = avg
137
        norm = dnorm[k]
138
        if avg > 0 and norm > 0:
139
            dc[k] /= norm
140
    return dc
141

    
142

    
143
k_nearest_neighbors = average_degree_connectivity