NetworkX

Source code for networkx.algorithms.block

# encoding: utf-8
"""
Functions for creating network blockmodels from node partitions.

Created by Drew Conway <drew.conway@nyu.edu> 
Copyright (c) 2010. All rights reserved.
"""
__author__ = """\n""".join(['Drew Conway <drew.conway@nyu.edu>',
                            'Aric Hagberg <hagberg@lanl.gov>'])
__all__=['blockmodel']

import networkx as nx

[docs]def blockmodel(G,partitions,multigraph=False): """Returns a reduced graph constructed using the generalized block modeling technique. The blockmodel technique collapses nodes into blocks based on a given partitioning of the node set. Each partition of nodes (block) is represented as a single node in the reduced graph. Edges between nodes in the block graph are added according to the edges in the original graph. If the parameter multigraph is False (the default) a single edge is added with a weight equal to the sum of the edge weights between nodes in the original graph The default is a weight of 1 if weights are not specified. If the parameter multigraph is True then multiple edges are added each with the edge data from the original graph. Parameters ---------- G : graph A networkx Graph or DiGraph partitions : list of lists, or list of sets The partition of the nodes. Must be non-overlapping. multigraph : bool, optional If True return a MultiGraph with the edge data of the original graph applied to each corresponding edge in the new graph. If False return a Graph with the sum of the edge weights, or a count of the edges if the original graph is unweighted. Returns ------- blockmodel : a Networkx graph object Examples -------- >>> G=nx.path_graph(6) >>> partition=[[0,1],[2,3],[4,5]] >>> M=nx.blockmodel(G,partition) References ---------- .. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj "Generalized Blockmodeling",Cambridge University Press, 2004. """ # Create sets of node partitions part=list(map(set,partitions)) # Check for overlapping node partitions u=set() for p1,p2 in zip(part[:-1],part[1:]): u.update(p1) #if not u.isdisjoint(p2): # Python 2.6 required if len (u.intersection(p2))>0: raise nx.NetworkXException("Overlapping node partitions.") # Initialize blockmodel graph if multigraph: if G.is_directed(): M=nx.MultiDiGraph() else: M=nx.MultiGraph() else: if G.is_directed(): M=nx.DiGraph() else: M=nx.Graph() # Add nodes and properties to blockmodel # The blockmodel nodes are node-induced subgraphs of G # Label them with integers starting at 0 for i,p in zip(range(len(part)),part): M.add_node(i) # The node-induced subgraph is stored as the node 'graph' attribute SG=G.subgraph(p) M.node[i]['graph']=SG M.node[i]['nnodes']=SG.number_of_nodes() M.node[i]['nedges']=SG.number_of_edges() M.node[i]['density']=nx.density(SG) # Create mapping between original node labels and new blockmodel node labels block_mapping={} for n in M: nodes_in_block=M.node[n]['graph'].nodes() block_mapping.update(dict.fromkeys(nodes_in_block,n)) # Add edges to block graph for u,v,d in G.edges(data=True): bmu=block_mapping[u] bmv=block_mapping[v] if bmu==bmv: # no self loops continue if multigraph: # For multigraphs add an edge for each edge in original graph M.add_edge(bmu,bmv,attr_dict=d) else: # For graphs and digraphs add single weighted edge weight=d.get('weight',1.0) # default to 1 if no weight specified if M.has_edge(bmu,bmv): M[bmu][bmv]['weight']+=weight else: M.add_edge(bmu,bmv,weight=weight) return M