# -*- coding: utf-8 -*-
"""One-mode (unipartite) projections of bipartite graphs.
"""
import networkx as nx
# Copyright (C) 2011 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
'Jordi Torrents <jtorrents@milnou.net>'])
__all__ = ['project',
'projected_graph',
'weighted_projected_graph',
'collaboration_weighted_projected_graph',
'overlap_weighted_projected_graph',
'generic_weighted_projected_graph']
[docs]def projected_graph(B, nodes, multigraph=False):
r"""Returns the projection of B onto one of its node sets.
Returns the graph G that is the projection of the bipartite graph B
onto the specified nodes. They retain their attributes and are connected
in G if they have a common neighbor in B.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto (the "bottom" nodes).
multigraph: bool (default=False)
If True return a multigraph where the multiple edges represent multiple
shared neighbors. They edge key in the multigraph is assigned to the
label of the neighbor.
Returns
-------
Graph : NetworkX graph or multigraph
A graph that is the projection onto the given nodes.
Examples
--------
>>> from networkx.algorithms import bipartite
>>> B = nx.path_graph(4)
>>> G = bipartite.projected_graph(B, [1,3])
>>> print(G.nodes())
[1, 3]
>>> print(G.edges())
[(1, 3)]
If nodes `a`, and `b` are connected through both nodes 1 and 2 then
building a multigraph results in two edges in the projection onto
[`a`,`b`]:
>>> B = nx.Graph()
>>> B.add_edges_from([('a', 1), ('b', 1), ('a', 2), ('b', 2)])
>>> G = bipartite.projected_graph(B, ['a', 'b'], multigraph=True)
>>> print([sorted((u,v)) for u,v in G.edges()])
[['a', 'b'], ['a', 'b']]
Notes
-----
No attempt is made to verify that the input graph B is bipartite.
Returns a simple graph that is the projection of the bipartite graph B
onto the set of nodes given in list nodes. If multigraph=True then
a multigraph is returned with an edge for every shared neighbor.
Directed graphs are allowed as input. The output will also then
be a directed graph with edges if there is a directed path between
the nodes.
The graph and node properties are (shallow) copied to the projected graph.
See Also
--------
is_bipartite,
is_bipartite_node_set,
sets,
weighted_projected_graph,
collaboration_weighted_projected_graph,
overlap_weighted_projected_graph,
generic_weighted_projected_graph
"""
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
directed=True
if multigraph:
G=nx.MultiDiGraph()
else:
G=nx.DiGraph()
else:
directed=False
if multigraph:
G=nx.MultiGraph()
else:
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
for u in nodes:
nbrs2=set((v for nbr in B[u] for v in B[nbr])) -set([u])
if multigraph:
for n in nbrs2:
if directed:
links=set(B[u]) & set(B.pred[n])
else:
links=set(B[u]) & set(B[n])
for l in links:
if not G.has_edge(u,n,l):
G.add_edge(u,n,key=l)
else:
G.add_edges_from((u,n) for n in nbrs2)
return G
[docs]def weighted_projected_graph(B, nodes, ratio=False):
r"""Returns a weighted projection of B onto one of its node sets.
The weighted projected graph is the projection of the bipartite
network B onto the specified nodes with weights representing the
number of shared neighbors or the ratio between actual shared
neighbors and possible shared neighbors if ratio=True [1]_. The
nodes retain their attributes and are connected in the resulting graph
if they have an edge to a common node in the original graph.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto (the "bottom" nodes).
ratio: Bool (default=False)
If True, edge weight is the ratio between actual shared neighbors
and possible shared neighbors. If False, edges weight is the number
of shared neighbors.
Returns
-------
Graph : NetworkX graph
A graph that is the projection onto the given nodes.
Examples
--------
>>> from networkx.algorithms import bipartite
>>> B = nx.path_graph(4)
>>> G = bipartite.weighted_projected_graph(B, [1,3])
>>> print(G.nodes())
[1, 3]
>>> print(G.edges(data=True))
[(1, 3, {'weight': 1})]
>>> G = bipartite.weighted_projected_graph(B, [1,3], ratio=True)
>>> print(G.edges(data=True))
[(1, 3, {'weight': 0.5})]
Notes
-----
No attempt is made to verify that the input graph B is bipartite.
The graph and node properties are (shallow) copied to the projected graph.
See Also
--------
is_bipartite,
is_bipartite_node_set,
sets,
collaboration_weighted_projected_graph,
overlap_weighted_projected_graph,
generic_weighted_projected_graph
projected_graph
References
----------
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
of Social Network Analysis. Sage Publications.
"""
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
pred=B.pred
G=nx.DiGraph()
else:
pred=B.adj
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
n_top = float(len(B) - len(nodes))
for u in nodes:
unbrs = set(B[u])
nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
for v in nbrs2:
vnbrs = set(pred[v])
common = unbrs & vnbrs
if not ratio:
weight = len(common)
else:
weight = len(common) / n_top
G.add_edge(u,v,weight=weight)
return G
[docs]def collaboration_weighted_projected_graph(B, nodes):
r"""Newman's weighted projection of B onto one of its node sets.
The collaboration weighted projection is the projection of the
bipartite network B onto the specified nodes with weights assigned
using Newman's collaboration model [1]_:
.. math::
w_{v,u} = \sum_k \frac{\delta_{v}^{w} \delta_{w}^{k}}{k_w - 1}
where `v` and `u` are nodes from the same bipartite node set,
and `w` is a node of the opposite node set.
The value `k_w` is the degree of node `w` in the bipartite
network and `\delta_{v}^{w}` is 1 if node `v` is
linked to node `w` in the original bipartite graph or 0 otherwise.
The nodes retain their attributes and are connected in the resulting
graph if have an edge to a common node in the original bipartite
graph.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto (the "bottom" nodes).
Returns
-------
Graph : NetworkX graph
A graph that is the projection onto the given nodes.
Examples
--------
>>> from networkx.algorithms import bipartite
>>> B = nx.path_graph(5)
>>> B.add_edge(1,5)
>>> G = bipartite.collaboration_weighted_projected_graph(B, [0, 2, 4, 5])
>>> print(G.nodes())
[0, 2, 4, 5]
>>> for edge in G.edges(data=True): print(edge)
...
(0, 2, {'weight': 0.5})
(0, 5, {'weight': 0.5})
(2, 4, {'weight': 1.0})
(2, 5, {'weight': 0.5})
Notes
-----
No attempt is made to verify that the input graph B is bipartite.
The graph and node properties are (shallow) copied to the projected graph.
See Also
--------
is_bipartite,
is_bipartite_node_set,
sets,
weighted_projected_graph,
overlap_weighted_projected_graph,
generic_weighted_projected_graph,
projected_graph
References
----------
.. [1] Scientific collaboration networks: II.
Shortest paths, weighted networks, and centrality,
M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).
"""
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
pred=B.pred
G=nx.DiGraph()
else:
pred=B.adj
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
for u in nodes:
unbrs = set(B[u])
nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
for v in nbrs2:
vnbrs = set(pred[v])
common = unbrs & vnbrs
weight = sum([1.0/(len(B[n]) - 1) for n in common if len(B[n])>1])
G.add_edge(u,v,weight=weight)
return G
[docs]def overlap_weighted_projected_graph(B, nodes, jaccard=True):
r"""Overlap weighted projection of B onto one of its node sets.
The overlap weighted projection is the projection of the bipartite
network B onto the specified nodes with weights representing
the Jaccard index between the neighborhoods of the two nodes in the
original bipartite network [1]_:
.. math::
w_{v,u} = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}
or if the parameter 'jaccard' is False, the fraction of common
neighbors by minimum of both nodes degree in the original
bipartite graph [1]_:
.. math::
w_{v,u} = \frac{|N(u) \cap N(v)|}{min(|N(u)|,|N(v)|)}
The nodes retain their attributes and are connected in the resulting
graph if have an edge to a common node in the original bipartite graph.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto (the "bottom" nodes).
jaccard: Bool (default=True)
Returns
-------
Graph : NetworkX graph
A graph that is the projection onto the given nodes.
Examples
--------
>>> from networkx.algorithms import bipartite
>>> B = nx.path_graph(5)
>>> G = bipartite.overlap_weighted_projected_graph(B, [0, 2, 4])
>>> print(G.nodes())
[0, 2, 4]
>>> print(G.edges(data=True))
[(0, 2, {'weight': 0.5}), (2, 4, {'weight': 0.5})]
>>> G = bipartite.overlap_weighted_projected_graph(B, [0, 2, 4], jaccard=False)
>>> print(G.edges(data=True))
[(0, 2, {'weight': 1.0}), (2, 4, {'weight': 1.0})]
Notes
-----
No attempt is made to verify that the input graph B is bipartite.
The graph and node properties are (shallow) copied to the projected graph.
See Also
--------
is_bipartite,
is_bipartite_node_set,
sets,
weighted_projected_graph,
collaboration_weighted_projected_graph,
generic_weighted_projected_graph,
projected_graph
References
----------
.. [1] Borgatti, S.P. and Halgin, D. In press. Analyzing Affiliation
Networks. In Carrington, P. and Scott, J. (eds) The Sage Handbook
of Social Network Analysis. Sage Publications.
"""
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
pred=B.pred
G=nx.DiGraph()
else:
pred=B.adj
G=nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
for u in nodes:
unbrs = set(B[u])
nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
for v in nbrs2:
vnbrs = set(pred[v])
if jaccard:
weight = float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
else:
weight = float(len(unbrs & vnbrs)) / min(len(unbrs),len(vnbrs))
G.add_edge(u,v,weight=weight)
return G
[docs]def generic_weighted_projected_graph(B, nodes, weight_function=None):
r"""Weighted projection of B with a user-specified weight function.
The bipartite network B is projected on to the specified nodes
with weights computed by a user-specified function. This function
must accept as a parameter the neighborhood sets of two nodes and
return an integer or a float.
The nodes retain their attributes and are connected in the resulting graph
if they have an edge to a common node in the original graph.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto (the "bottom" nodes).
weight_function: function
This function must accept as parameters the same input graph
that this function, and two nodes; and return an integer or a float.
The default function computes the number of shared neighbors.
Returns
-------
Graph : NetworkX graph
A graph that is the projection onto the given nodes.
Examples
--------
>>> from networkx.algorithms import bipartite
>>> # Define some custom weight functions
>>> def jaccard(G, u, v):
... unbrs = set(G[u])
... vnbrs = set(G[v])
... return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
...
>>> def my_weight(G, u, v, weight='weight'):
... w = 0
... for nbr in set(G[u]) & set(G[v]):
... w += G.edge[u][nbr].get(weight, 1) + G.edge[v][nbr].get(weight, 1)
... return w
...
>>> # A complete bipartite graph with 4 nodes and 4 edges
>>> B = nx.complete_bipartite_graph(2,2)
>>> # Add some arbitrary weight to the edges
>>> for i,(u,v) in enumerate(B.edges()):
... B.edge[u][v]['weight'] = i + 1
...
>>> for edge in B.edges(data=True):
... print(edge)
...
(0, 2, {'weight': 1})
(0, 3, {'weight': 2})
(1, 2, {'weight': 3})
(1, 3, {'weight': 4})
>>> # Without specifying a function, the weight is equal to # shared partners
>>> G = bipartite.generic_weighted_projected_graph(B, [0, 1])
>>> print(G.edges(data=True))
[(0, 1, {'weight': 2})]
>>> # To specify a custom weight function use the weight_function parameter
>>> G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=jaccard)
>>> print(G.edges(data=True))
[(0, 1, {'weight': 1.0})]
>>> G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=my_weight)
>>> print(G.edges(data=True))
[(0, 1, {'weight': 10})]
Notes
-----
No attempt is made to verify that the input graph B is bipartite.
The graph and node properties are (shallow) copied to the projected graph.
See Also
--------
is_bipartite,
is_bipartite_node_set,
sets,
weighted_projected_graph,
collaboration_weighted_projected_graph,
overlap_weighted_projected_graph,
projected_graph
"""
if B.is_multigraph():
raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
pred=B.pred
G=nx.DiGraph()
else:
pred=B.adj
G=nx.Graph()
if weight_function is None:
def weight_function(G, u, v):
# Notice that we use set(pred[v]) for handling the directed case.
return len(set(G[u]) & set(pred[v]))
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in nodes)
for u in nodes:
nbrs2 = set((n for nbr in set(B[u]) for n in B[nbr])) - set([u])
for v in nbrs2:
weight = weight_function(B, u, v)
G.add_edge(u,v,weight=weight)
return G
def project(B, nodes, create_using=None):
return projected_graph(B, nodes)