Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.bipartite.projection

# -*- 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)