Source code for networkx.algorithms.block
# encoding: utf-8
Functions for creating network blockmodels from node partitions.
Created by Drew Conway <firstname.lastname@example.org>
Copyright (c) 2010. All rights reserved.
__author__ = """\n""".join(['Drew Conway <email@example.com>',
'Aric Hagberg <firstname.lastname@example.org>'])
import networkx as nx
"""Returns a reduced graph constructed using the generalized block modeling
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.
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.
blockmodel : a Networkx graph object
..  Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj
"Generalized Blockmodeling",Cambridge University Press, 2004.
# Create sets of node partitions
# Check for overlapping node partitions
for p1,p2 in zip(part[:-1],part[1:]):
#if not u.isdisjoint(p2): # Python 2.6 required
if len (u.intersection(p2))>0:
raise nx.NetworkXException("Overlapping node partitions.")
# Initialize blockmodel 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):
# The node-induced subgraph is stored as the node 'graph' attribute
# Create mapping between original node labels and new blockmodel node labels
for n in M:
# Add edges to block graph
for u,v,d in G.edges(data=True):
if bmu==bmv: # no self loops
# For multigraphs add an edge for each edge in original graph
# For graphs and digraphs add single weighted edge
weight=d.get('weight',1.0) # default to 1 if no weight specified