Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bipartite / projection.py @ 5cef0f13

History | View | Annotate | Download (16.4 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2017-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Aric Hagberg <aric.hagberg@gmail.com>
10
#          Jordi Torrents <jtorrents@milnou.net>
11
"""One-mode (unipartite) projections of bipartite graphs."""
12
import networkx as nx
13
from networkx.utils import not_implemented_for
14

    
15
__all__ = ['project',
16
           'projected_graph',
17
           'weighted_projected_graph',
18
           'collaboration_weighted_projected_graph',
19
           'overlap_weighted_projected_graph',
20
           'generic_weighted_projected_graph']
21

    
22

    
23
def projected_graph(B, nodes, multigraph=False):
24
    r"""Returns the projection of B onto one of its node sets.
25

26
    Returns the graph G that is the projection of the bipartite graph B
27
    onto the specified nodes. They retain their attributes and are connected
28
    in G if they have a common neighbor in B.
29

30
    Parameters
31
    ----------
32
    B : NetworkX graph
33
      The input graph should be bipartite.
34

35
    nodes : list or iterable
36
      Nodes to project onto (the "bottom" nodes).
37

38
    multigraph: bool (default=False)
39
       If True return a multigraph where the multiple edges represent multiple
40
       shared neighbors.  They edge key in the multigraph is assigned to the
41
       label of the neighbor.
42

43
    Returns
44
    -------
45
    Graph : NetworkX graph or multigraph
46
       A graph that is the projection onto the given nodes.
47

48
    Examples
49
    --------
50
    >>> from networkx.algorithms import bipartite
51
    >>> B = nx.path_graph(4)
52
    >>> G = bipartite.projected_graph(B, [1, 3])
53
    >>> list(G)
54
    [1, 3]
55
    >>> list(G.edges())
56
    [(1, 3)]
57

58
    If nodes `a`, and `b` are connected through both nodes 1 and 2 then
59
    building a multigraph results in two edges in the projection onto
60
    [`a`, `b`]:
61

62
    >>> B = nx.Graph()
63
    >>> B.add_edges_from([('a', 1), ('b', 1), ('a', 2), ('b', 2)])
64
    >>> G = bipartite.projected_graph(B, ['a', 'b'], multigraph=True)
65
    >>> print([sorted((u, v)) for u, v in G.edges()])
66
    [['a', 'b'], ['a', 'b']]
67

68
    Notes
69
    -----
70
    No attempt is made to verify that the input graph B is bipartite.
71
    Returns a simple graph that is the projection of the bipartite graph B
72
    onto the set of nodes given in list nodes.  If multigraph=True then
73
    a multigraph is returned with an edge for every shared neighbor.
74

75
    Directed graphs are allowed as input.  The output will also then
76
    be a directed graph with edges if there is a directed path between
77
    the nodes.
78

79
    The graph and node properties are (shallow) copied to the projected graph.
80

81
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
82
    for further details on how bipartite graphs are handled in NetworkX.
83

84
    See Also
85
    --------
86
    is_bipartite,
87
    is_bipartite_node_set,
88
    sets,
89
    weighted_projected_graph,
90
    collaboration_weighted_projected_graph,
91
    overlap_weighted_projected_graph,
92
    generic_weighted_projected_graph
93
    """
94
    if B.is_multigraph():
95
        raise nx.NetworkXError("not defined for multigraphs")
96
    if B.is_directed():
97
        directed = True
98
        if multigraph:
99
            G = nx.MultiDiGraph()
100
        else:
101
            G = nx.DiGraph()
102
    else:
103
        directed = False
104
        if multigraph:
105
            G = nx.MultiGraph()
106
        else:
107
            G = nx.Graph()
108
    G.graph.update(B.graph)
109
    G.add_nodes_from((n, B.nodes[n]) for n in nodes)
110
    for u in nodes:
111
        nbrs2 = set(v for nbr in B[u] for v in B[nbr] if v != u)
112
        if multigraph:
113
            for n in nbrs2:
114
                if directed:
115
                    links = set(B[u]) & set(B.pred[n])
116
                else:
117
                    links = set(B[u]) & set(B[n])
118
                for l in links:
119
                    if not G.has_edge(u, n, l):
120
                        G.add_edge(u, n, key=l)
121
        else:
122
            G.add_edges_from((u, n) for n in nbrs2)
123
    return G
124

    
125

    
126
@not_implemented_for('multigraph')
127
def weighted_projected_graph(B, nodes, ratio=False):
128
    r"""Returns a weighted projection of B onto one of its node sets.
129

130
    The weighted projected graph is the projection of the bipartite
131
    network B onto the specified nodes with weights representing the
132
    number of shared neighbors or the ratio between actual shared
133
    neighbors and possible shared neighbors if ``ratio is True`` [1]_.
134
    The nodes retain their attributes and are connected in the resulting
135
    graph if they have an edge to a common node in the original graph.
136

137
    Parameters
138
    ----------
139
    B : NetworkX graph
140
        The input graph should be bipartite.
141

142
    nodes : list or iterable
143
        Nodes to project onto (the "bottom" nodes).
144

145
    ratio: Bool (default=False)
146
        If True, edge weight is the ratio between actual shared neighbors
147
        and maximum possible shared neighbors (i.e., the size of the other 
148
        node set). If False, edges weight is the number of shared neighbors.
149

150
    Returns
151
    -------
152
    Graph : NetworkX graph
153
       A graph that is the projection onto the given nodes.
154

155
    Examples
156
    --------
157
    >>> from networkx.algorithms import bipartite
158
    >>> B = nx.path_graph(4)
159
    >>> G = bipartite.weighted_projected_graph(B, [1, 3])
160
    >>> list(G)
161
    [1, 3]
162
    >>> list(G.edges(data=True))
163
    [(1, 3, {'weight': 1})]
164
    >>> G = bipartite.weighted_projected_graph(B, [1, 3], ratio=True)
165
    >>> list(G.edges(data=True))
166
    [(1, 3, {'weight': 0.5})]
167

168
    Notes
169
    -----
170
    No attempt is made to verify that the input graph B is bipartite.
171
    The graph and node properties are (shallow) copied to the projected graph.
172

173
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
174
    for further details on how bipartite graphs are handled in NetworkX.
175

176
    See Also
177
    --------
178
    is_bipartite,
179
    is_bipartite_node_set,
180
    sets,
181
    collaboration_weighted_projected_graph,
182
    overlap_weighted_projected_graph,
183
    generic_weighted_projected_graph
184
    projected_graph
185

186
    References
187
    ----------
188
    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
189
        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
190
        of Social Network Analysis. Sage Publications.
191
    """
192
    if B.is_directed():
193
        pred = B.pred
194
        G = nx.DiGraph()
195
    else:
196
        pred = B.adj
197
        G = nx.Graph()
198
    G.graph.update(B.graph)
199
    G.add_nodes_from((n, B.nodes[n]) for n in nodes)
200
    n_top = float(len(B) - len(nodes))
201
    for u in nodes:
202
        unbrs = set(B[u])
203
        nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
204
        for v in nbrs2:
205
            vnbrs = set(pred[v])
206
            common = unbrs & vnbrs
207
            if not ratio:
208
                weight = len(common)
209
            else:
210
                weight = len(common) / n_top
211
            G.add_edge(u, v, weight=weight)
212
    return G
213

    
214

    
215
@not_implemented_for('multigraph')
216
def collaboration_weighted_projected_graph(B, nodes):
217
    r"""Newman's weighted projection of B onto one of its node sets.
218

219
    The collaboration weighted projection is the projection of the
220
    bipartite network B onto the specified nodes with weights assigned
221
    using Newman's collaboration model [1]_:
222

223
    .. math::
224

225
        w_{u, v} = \sum_k \frac{\delta_{u}^{k} \delta_{v}^{k}}{d_k - 1}
226

227
    where `u` and `v` are nodes from the bottom bipartite node set,
228
    and `k` is a node of the top node set.
229
    The value `d_k` is the degree of node `k` in the bipartite
230
    network and `\delta_{u}^{k}` is 1 if node `u` is
231
    linked to node `k` in the original bipartite graph or 0 otherwise.
232

233
    The nodes retain their attributes and are connected in the resulting
234
    graph if have an edge to a common node in the original bipartite
235
    graph.
236

237
    Parameters
238
    ----------
239
    B : NetworkX graph
240
      The input graph should be bipartite.
241

242
    nodes : list or iterable
243
      Nodes to project onto (the "bottom" nodes).
244

245
    Returns
246
    -------
247
    Graph : NetworkX graph
248
       A graph that is the projection onto the given nodes.
249

250
    Examples
251
    --------
252
    >>> from networkx.algorithms import bipartite
253
    >>> B = nx.path_graph(5)
254
    >>> B.add_edge(1, 5)
255
    >>> G = bipartite.collaboration_weighted_projected_graph(B, [0, 2, 4, 5])
256
    >>> list(G)
257
    [0, 2, 4, 5]
258
    >>> for edge in G.edges(data=True): print(edge)
259
    ...
260
    (0, 2, {'weight': 0.5})
261
    (0, 5, {'weight': 0.5})
262
    (2, 4, {'weight': 1.0})
263
    (2, 5, {'weight': 0.5})
264

265
    Notes
266
    -----
267
    No attempt is made to verify that the input graph B is bipartite.
268
    The graph and node properties are (shallow) copied to the projected graph.
269

270
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
271
    for further details on how bipartite graphs are handled in NetworkX.
272

273
    See Also
274
    --------
275
    is_bipartite,
276
    is_bipartite_node_set,
277
    sets,
278
    weighted_projected_graph,
279
    overlap_weighted_projected_graph,
280
    generic_weighted_projected_graph,
281
    projected_graph
282

283
    References
284
    ----------
285
    .. [1] Scientific collaboration networks: II.
286
        Shortest paths, weighted networks, and centrality,
287
        M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).
288
    """
289
    if B.is_directed():
290
        pred = B.pred
291
        G = nx.DiGraph()
292
    else:
293
        pred = B.adj
294
        G = nx.Graph()
295
    G.graph.update(B.graph)
296
    G.add_nodes_from((n, B.nodes[n]) for n in nodes)
297
    for u in nodes:
298
        unbrs = set(B[u])
299
        nbrs2 = set(n for nbr in unbrs for n in B[nbr] if n != u)
300
        for v in nbrs2:
301
            vnbrs = set(pred[v])
302
            common_degree = (len(B[n]) for n in unbrs & vnbrs)
303
            weight = sum(1.0 / (deg - 1) for deg in common_degree if deg > 1)
304
            G.add_edge(u, v, weight=weight)
305
    return G
306

    
307

    
308
@not_implemented_for('multigraph')
309
def overlap_weighted_projected_graph(B, nodes, jaccard=True):
310
    r"""Overlap weighted projection of B onto one of its node sets.
311

312
    The overlap weighted projection is the projection of the bipartite
313
    network B onto the specified nodes with weights representing
314
    the Jaccard index between the neighborhoods of the two nodes in the
315
    original bipartite network [1]_:
316

317
    .. math::
318

319
        w_{v, u} = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}
320

321
    or if the parameter 'jaccard' is False, the fraction of common
322
    neighbors by minimum of both nodes degree in the original
323
    bipartite graph [1]_:
324

325
    .. math::
326

327
        w_{v, u} = \frac{|N(u) \cap N(v)|}{min(|N(u)|, |N(v)|)}
328

329
    The nodes retain their attributes and are connected in the resulting
330
    graph if have an edge to a common node in the original bipartite graph.
331

332
    Parameters
333
    ----------
334
    B : NetworkX graph
335
        The input graph should be bipartite.
336

337
    nodes : list or iterable
338
        Nodes to project onto (the "bottom" nodes).
339

340
    jaccard: Bool (default=True)
341

342
    Returns
343
    -------
344
    Graph : NetworkX graph
345
       A graph that is the projection onto the given nodes.
346

347
    Examples
348
    --------
349
    >>> from networkx.algorithms import bipartite
350
    >>> B = nx.path_graph(5)
351
    >>> nodes = [0, 2, 4]
352
    >>> G = bipartite.overlap_weighted_projected_graph(B, nodes)
353
    >>> list(G)
354
    [0, 2, 4]
355
    >>> list(G.edges(data=True))
356
    [(0, 2, {'weight': 0.5}), (2, 4, {'weight': 0.5})]
357
    >>> G = bipartite.overlap_weighted_projected_graph(B, nodes, jaccard=False)
358
    >>> list(G.edges(data=True))
359
    [(0, 2, {'weight': 1.0}), (2, 4, {'weight': 1.0})]
360

361
    Notes
362
    -----
363
    No attempt is made to verify that the input graph B is bipartite.
364
    The graph and node properties are (shallow) copied to the projected graph.
365

366
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
367
    for further details on how bipartite graphs are handled in NetworkX.
368

369
    See Also
370
    --------
371
    is_bipartite,
372
    is_bipartite_node_set,
373
    sets,
374
    weighted_projected_graph,
375
    collaboration_weighted_projected_graph,
376
    generic_weighted_projected_graph,
377
    projected_graph
378

379
    References
380
    ----------
381
    .. [1] Borgatti, S.P. and Halgin, D. In press. Analyzing Affiliation
382
        Networks. In Carrington, P. and Scott, J. (eds) The Sage Handbook
383
        of Social Network Analysis. Sage Publications.
384

385
    """
386
    if B.is_directed():
387
        pred = B.pred
388
        G = nx.DiGraph()
389
    else:
390
        pred = B.adj
391
        G = nx.Graph()
392
    G.graph.update(B.graph)
393
    G.add_nodes_from((n, B.nodes[n]) for n in nodes)
394
    for u in nodes:
395
        unbrs = set(B[u])
396
        nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
397
        for v in nbrs2:
398
            vnbrs = set(pred[v])
399
            if jaccard:
400
                wt = float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
401
            else:
402
                wt = float(len(unbrs & vnbrs)) / min(len(unbrs), len(vnbrs))
403
            G.add_edge(u, v, weight=wt)
404
    return G
405

    
406

    
407
@not_implemented_for('multigraph')
408
def generic_weighted_projected_graph(B, nodes, weight_function=None):
409
    r"""Weighted projection of B with a user-specified weight function.
410

411
    The bipartite network B is projected on to the specified nodes
412
    with weights computed by a user-specified function.  This function
413
    must accept as a parameter the neighborhood sets of two nodes and
414
    return an integer or a float.
415

416
    The nodes retain their attributes and are connected in the resulting graph
417
    if they have an edge to a common node in the original graph.
418

419
    Parameters
420
    ----------
421
    B : NetworkX graph
422
        The input graph should be bipartite.
423

424
    nodes : list or iterable
425
        Nodes to project onto (the "bottom" nodes).
426

427
    weight_function : function
428
        This function must accept as parameters the same input graph
429
        that this function, and two nodes; and return an integer or a float.
430
        The default function computes the number of shared neighbors.
431

432
    Returns
433
    -------
434
    Graph : NetworkX graph
435
       A graph that is the projection onto the given nodes.
436

437
    Examples
438
    --------
439
    >>> from networkx.algorithms import bipartite
440
    >>> # Define some custom weight functions
441
    >>> def jaccard(G, u, v):
442
    ...     unbrs = set(G[u])
443
    ...     vnbrs = set(G[v])
444
    ...     return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
445
    ...
446
    >>> def my_weight(G, u, v, weight='weight'):
447
    ...     w = 0
448
    ...     for nbr in set(G[u]) & set(G[v]):
449
    ...         w += G[u][nbr].get(weight, 1) + G[v][nbr].get(weight, 1)
450
    ...     return w
451
    ...
452
    >>> # A complete bipartite graph with 4 nodes and 4 edges
453
    >>> B = nx.complete_bipartite_graph(2, 2)
454
    >>> # Add some arbitrary weight to the edges
455
    >>> for i,(u,v) in enumerate(B.edges()):
456
    ...     B.edges[u, v]['weight'] = i + 1
457
    ... 
458
    >>> for edge in B.edges(data=True):
459
    ...     print(edge)
460
    ...
461
    (0, 2, {'weight': 1})
462
    (0, 3, {'weight': 2})
463
    (1, 2, {'weight': 3})
464
    (1, 3, {'weight': 4})
465
    >>> # By default, the weight is the number of shared neighbors
466
    >>> G = bipartite.generic_weighted_projected_graph(B, [0, 1])
467
    >>> print(list(G.edges(data=True)))
468
    [(0, 1, {'weight': 2})]
469
    >>> # To specify a custom weight function use the weight_function parameter
470
    >>> G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=jaccard)
471
    >>> print(list(G.edges(data=True)))
472
    [(0, 1, {'weight': 1.0})]
473
    >>> G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=my_weight)
474
    >>> print(list(G.edges(data=True)))
475
    [(0, 1, {'weight': 10})]
476

477
    Notes
478
    -----
479
    No attempt is made to verify that the input graph B is bipartite.
480
    The graph and node properties are (shallow) copied to the projected graph.
481

482
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
483
    for further details on how bipartite graphs are handled in NetworkX.
484

485
    See Also
486
    --------
487
    is_bipartite,
488
    is_bipartite_node_set,
489
    sets,
490
    weighted_projected_graph,
491
    collaboration_weighted_projected_graph,
492
    overlap_weighted_projected_graph,
493
    projected_graph
494

495
    """
496
    if B.is_directed():
497
        pred = B.pred
498
        G = nx.DiGraph()
499
    else:
500
        pred = B.adj
501
        G = nx.Graph()
502
    if weight_function is None:
503
        def weight_function(G, u, v):
504
            # Notice that we use set(pred[v]) for handling the directed case.
505
            return len(set(G[u]) & set(pred[v]))
506
    G.graph.update(B.graph)
507
    G.add_nodes_from((n, B.nodes[n]) for n in nodes)
508
    for u in nodes:
509
        nbrs2 = set((n for nbr in set(B[u]) for n in B[nbr])) - set([u])
510
        for v in nbrs2:
511
            weight = weight_function(B, u, v)
512
            G.add_edge(u, v, weight=weight)
513
    return G
514

    
515

    
516
def project(B, nodes, create_using=None):
517
    return projected_graph(B, nodes)