← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/assortativity/connectivity.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/assortativity/connectivity.py
 
1
#-*- coding: utf-8 -*-
 
2
#    Copyright (C) 2011 by 
 
3
#    Jordi Torrents <jtorrents@milnou.net>
 
4
#    Aric Hagberg <hagberg@lanl.gov>
 
5
#    All rights reserved.
 
6
#    BSD license.
 
7
from collections import defaultdict
 
8
import networkx as nx
 
9
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
 
10
                            'Aric Hagberg (hagberg@lanl.gov)'])
 
11
__all__ = ['average_degree_connectivity',
 
12
           'k_nearest_neighbors']
 
13
 
 
14
def _avg_deg_conn(G, neighbors, source_degree, target_degree, 
 
15
                  nodes=None, weight=None):
 
16
    # "k nearest neighbors, or neighbor_connectivity
 
17
    dsum = defaultdict(float)
 
18
    dnorm = defaultdict(float)
 
19
    for n,k in source_degree(nodes).items():
 
20
        nbrdeg = target_degree(neighbors(n))
 
21
        if weight is None:
 
22
            s = float(sum(nbrdeg.values()))
 
23
        else: # weight nbr degree by weight of (n,nbr) edge
 
24
            s = float(sum((G[n][nbr].get(weight,1)*d 
 
25
                           for nbr,d in nbrdeg.items())))
 
26
        dnorm[k] += source_degree(n, weight=weight)
 
27
        dsum[k] += s
 
28
        
 
29
    # normalize
 
30
    dc = {}
 
31
    for k,avg in dsum.items():
 
32
        dc[k]=avg
 
33
        norm = dnorm[k]
 
34
        if avg > 0 and norm > 0:
 
35
            dc[k]/=norm
 
36
    return dc
 
37
 
 
38
def average_degree_connectivity(G, source="in+out", target="in+out",
 
39
                                nodes=None, weight=None):
 
40
    r"""Compute the average degree connectivity of graph.
 
41
 
 
42
    The average degree connectivity is the average nearest neighbor degree of
 
43
    nodes with degree k. For weighted graphs, an analogous measure can 
 
44
    be computed using the weighted average neighbors degree defined in 
 
45
    [1]_, for a node `i`, as:
 
46
 
 
47
    .. math::
 
48
 
 
49
        k_{nn,i}^{w} = \frac{1}{s_i} \sum_{j \in N(i)} w_{ij} k_j
 
50
 
 
51
    where `s_i` is the weighted degree of node `i`, 
 
52
    `w_{ij}` is the weight of the edge that links `i` and `j`,
 
53
    and `N(i)` are the neighbors of node `i`.
 
54
 
 
55
    Parameters
 
56
    ----------
 
57
    G : NetworkX graph
 
58
 
 
59
    source :  "in"|"out"|"in+out" (default:"in+out")
 
60
       Directed graphs only. Use "in"- or "out"-degree for source node.
 
61
 
 
62
    target : "in"|"out"|"in+out" (default:"in+out"
 
63
       Directed graphs only. Use "in"- or "out"-degree for target node.
 
64
 
 
65
    nodes: list or iterable (optional)
 
66
        Compute neighbor connectivity for these nodes. The default is all nodes.
 
67
 
 
68
    weight : string or None, optional (default=None)
 
69
       The edge attribute that holds the numerical value used as a weight.
 
70
       If None, then each edge has weight 1.
 
71
 
 
72
    Returns
 
73
    -------
 
74
    d: dict
 
75
       A dictionary keyed by degree k with the value of average connectivity.
 
76
    
 
77
    Examples
 
78
    --------
 
79
    >>> G=nx.path_graph(4)
 
80
    >>> G.edge[1][2]['weight'] = 3
 
81
    >>> nx.k_nearest_neighbors(G)
 
82
    {1: 2.0, 2: 1.5}
 
83
    >>> nx.k_nearest_neighbors(G, weight='weight')
 
84
    {1: 2.0, 2: 1.75}
 
85
 
 
86
    See also
 
87
    --------
 
88
    neighbors_average_degree
 
89
 
 
90
    Notes
 
91
    -----
 
92
    This algorithm is sometimes called "k nearest neighbors'.
 
93
 
 
94
    References
 
95
    ----------    
 
96
    .. [1] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, 
 
97
       "The architecture of complex weighted networks". 
 
98
       PNAS 101 (11): 3747–3752 (2004).
 
99
    """
 
100
    source_degree = G.degree
 
101
    target_degree = G.degree
 
102
    neighbors = G.neighbors
 
103
    if G.is_directed():
 
104
        direction = {'out':G.out_degree,
 
105
                     'in':G.in_degree,
 
106
                     'in+out': G.degree}
 
107
        source_degree = direction[source]
 
108
        target_degree = direction[target]
 
109
        if source == 'in':
 
110
            neighbors=G.predecessors
 
111
        elif source == 'out':
 
112
            neighbors=G.successors
 
113
    return _avg_deg_conn(G, neighbors, source_degree, target_degree,
 
114
                         nodes=nodes, weight=weight)
 
115
 
 
116
k_nearest_neighbors=average_degree_connectivity