ioftools / networkxMiCe / networkxmaster / networkx / algorithms / assortativity / connectivity.py @ 5cef0f13
History  View  Annotate  Download (4.46 KB)
1 
# * coding: utf8 *


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. PastorSatorras, 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 inedge 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 