225 lines
8.0 KiB
Python
225 lines
8.0 KiB
Python
|
"""
|
||
|
|
Moody and White algorithm for k-components
|
||
|
|
"""
|
||
|
|
from collections import defaultdict
|
||
|
|
from itertools import combinations
|
||
|
|
from operator import itemgetter
|
||
|
|
|
||
|
|
import networkx as nx
|
||
|
|
|
||
|
|
# Define the default maximum flow function.
|
||
|
|
from networkx.algorithms.flow import edmonds_karp
|
||
|
|
from networkx.utils import not_implemented_for
|
||
|
|
|
||
|
|
default_flow_func = edmonds_karp
|
||
|
|
|
||
|
|
__all__ = ["k_components"]
|
||
|
|
|
||
|
|
|
||
|
|
@not_implemented_for("directed")
|
||
|
|
def k_components(G, flow_func=None):
|
||
|
|
r"""Returns the k-component structure of a graph G.
|
||
|
|
|
||
|
|
A `k`-component is a maximal subgraph of a graph G that has, at least,
|
||
|
|
node connectivity `k`: we need to remove at least `k` nodes to break it
|
||
|
|
into more components. `k`-components have an inherent hierarchical
|
||
|
|
structure because they are nested in terms of connectivity: a connected
|
||
|
|
graph can contain several 2-components, each of which can contain
|
||
|
|
one or more 3-components, and so forth.
|
||
|
|
|
||
|
|
Parameters
|
||
|
|
----------
|
||
|
|
G : NetworkX graph
|
||
|
|
|
||
|
|
flow_func : function
|
||
|
|
Function to perform the underlying flow computations. Default value
|
||
|
|
:meth:`edmonds_karp`. This function performs better in sparse graphs with
|
||
|
|
right tailed degree distributions. :meth:`shortest_augmenting_path` will
|
||
|
|
perform better in denser graphs.
|
||
|
|
|
||
|
|
Returns
|
||
|
|
-------
|
||
|
|
k_components : dict
|
||
|
|
Dictionary with all connectivity levels `k` in the input Graph as keys
|
||
|
|
and a list of sets of nodes that form a k-component of level `k` as
|
||
|
|
values.
|
||
|
|
|
||
|
|
Raises
|
||
|
|
------
|
||
|
|
NetworkXNotImplemented
|
||
|
|
If the input graph is directed.
|
||
|
|
|
||
|
|
Examples
|
||
|
|
--------
|
||
|
|
>>> # Petersen graph has 10 nodes and it is triconnected, thus all
|
||
|
|
>>> # nodes are in a single component on all three connectivity levels
|
||
|
|
>>> G = nx.petersen_graph()
|
||
|
|
>>> k_components = nx.k_components(G)
|
||
|
|
|
||
|
|
Notes
|
||
|
|
-----
|
||
|
|
Moody and White [1]_ (appendix A) provide an algorithm for identifying
|
||
|
|
k-components in a graph, which is based on Kanevsky's algorithm [2]_
|
||
|
|
for finding all minimum-size node cut-sets of a graph (implemented in
|
||
|
|
:meth:`all_node_cuts` function):
|
||
|
|
|
||
|
|
1. Compute node connectivity, k, of the input graph G.
|
||
|
|
|
||
|
|
2. Identify all k-cutsets at the current level of connectivity using
|
||
|
|
Kanevsky's algorithm.
|
||
|
|
|
||
|
|
3. Generate new graph components based on the removal of
|
||
|
|
these cutsets. Nodes in a cutset belong to both sides
|
||
|
|
of the induced cut.
|
||
|
|
|
||
|
|
4. If the graph is neither complete nor trivial, return to 1;
|
||
|
|
else end.
|
||
|
|
|
||
|
|
This implementation also uses some heuristics (see [3]_ for details)
|
||
|
|
to speed up the computation.
|
||
|
|
|
||
|
|
See also
|
||
|
|
--------
|
||
|
|
node_connectivity
|
||
|
|
all_node_cuts
|
||
|
|
biconnected_components : special case of this function when k=2
|
||
|
|
k_edge_components : similar to this function, but uses edge-connectivity
|
||
|
|
instead of node-connectivity
|
||
|
|
|
||
|
|
References
|
||
|
|
----------
|
||
|
|
.. [1] Moody, J. and D. White (2003). Social cohesion and embeddedness:
|
||
|
|
A hierarchical conception of social groups.
|
||
|
|
American Sociological Review 68(1), 103--28.
|
||
|
|
http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf
|
||
|
|
|
||
|
|
.. [2] Kanevsky, A. (1993). Finding all minimum-size separating vertex
|
||
|
|
sets in a graph. Networks 23(6), 533--541.
|
||
|
|
http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract
|
||
|
|
|
||
|
|
.. [3] Torrents, J. and F. Ferraro (2015). Structural Cohesion:
|
||
|
|
Visualization and Heuristics for Fast Computation.
|
||
|
|
https://arxiv.org/pdf/1503.04476v1
|
||
|
|
|
||
|
|
"""
|
||
|
|
# Dictionary with connectivity level (k) as keys and a list of
|
||
|
|
# sets of nodes that form a k-component as values. Note that
|
||
|
|
# k-compoents can overlap (but only k - 1 nodes).
|
||
|
|
k_components = defaultdict(list)
|
||
|
|
# Define default flow function
|
||
|
|
if flow_func is None:
|
||
|
|
flow_func = default_flow_func
|
||
|
|
# Bicomponents as a base to check for higher order k-components
|
||
|
|
for component in nx.connected_components(G):
|
||
|
|
# isolated nodes have connectivity 0
|
||
|
|
comp = set(component)
|
||
|
|
if len(comp) > 1:
|
||
|
|
k_components[1].append(comp)
|
||
|
|
bicomponents = [G.subgraph(c) for c in nx.biconnected_components(G)]
|
||
|
|
for bicomponent in bicomponents:
|
||
|
|
bicomp = set(bicomponent)
|
||
|
|
# avoid considering dyads as bicomponents
|
||
|
|
if len(bicomp) > 2:
|
||
|
|
k_components[2].append(bicomp)
|
||
|
|
for B in bicomponents:
|
||
|
|
if len(B) <= 2:
|
||
|
|
continue
|
||
|
|
k = nx.node_connectivity(B, flow_func=flow_func)
|
||
|
|
if k > 2:
|
||
|
|
k_components[k].append(set(B))
|
||
|
|
# Perform cuts in a DFS like order.
|
||
|
|
cuts = list(nx.all_node_cuts(B, k=k, flow_func=flow_func))
|
||
|
|
stack = [(k, _generate_partition(B, cuts, k))]
|
||
|
|
while stack:
|
||
|
|
(parent_k, partition) = stack[-1]
|
||
|
|
try:
|
||
|
|
nodes = next(partition)
|
||
|
|
C = B.subgraph(nodes)
|
||
|
|
this_k = nx.node_connectivity(C, flow_func=flow_func)
|
||
|
|
if this_k > parent_k and this_k > 2:
|
||
|
|
k_components[this_k].append(set(C))
|
||
|
|
cuts = list(nx.all_node_cuts(C, k=this_k, flow_func=flow_func))
|
||
|
|
if cuts:
|
||
|
|
stack.append((this_k, _generate_partition(C, cuts, this_k)))
|
||
|
|
except StopIteration:
|
||
|
|
stack.pop()
|
||
|
|
|
||
|
|
# This is necessary because k-components may only be reported at their
|
||
|
|
# maximum k level. But we want to return a dictionary in which keys are
|
||
|
|
# connectivity levels and values list of sets of components, without
|
||
|
|
# skipping any connectivity level. Also, it's possible that subsets of
|
||
|
|
# an already detected k-component appear at a level k. Checking for this
|
||
|
|
# in the while loop above penalizes the common case. Thus we also have to
|
||
|
|
# _consolidate all connectivity levels in _reconstruct_k_components.
|
||
|
|
return _reconstruct_k_components(k_components)
|
||
|
|
|
||
|
|
|
||
|
|
def _consolidate(sets, k):
|
||
|
|
"""Merge sets that share k or more elements.
|
||
|
|
|
||
|
|
See: http://rosettacode.org/wiki/Set_consolidation
|
||
|
|
|
||
|
|
The iterative python implementation posted there is
|
||
|
|
faster than this because of the overhead of building a
|
||
|
|
Graph and calling nx.connected_components, but it's not
|
||
|
|
clear for us if we can use it in NetworkX because there
|
||
|
|
is no licence for the code.
|
||
|
|
|
||
|
|
"""
|
||
|
|
G = nx.Graph()
|
||
|
|
nodes = {i: s for i, s in enumerate(sets)}
|
||
|
|
G.add_nodes_from(nodes)
|
||
|
|
G.add_edges_from(
|
||
|
|
(u, v) for u, v in combinations(nodes, 2) if len(nodes[u] & nodes[v]) >= k
|
||
|
|
)
|
||
|
|
for component in nx.connected_components(G):
|
||
|
|
yield set.union(*[nodes[n] for n in component])
|
||
|
|
|
||
|
|
|
||
|
|
def _generate_partition(G, cuts, k):
|
||
|
|
def has_nbrs_in_partition(G, node, partition):
|
||
|
|
for n in G[node]:
|
||
|
|
if n in partition:
|
||
|
|
return True
|
||
|
|
return False
|
||
|
|
|
||
|
|
components = []
|
||
|
|
nodes = {n for n, d in G.degree() if d > k} - {n for cut in cuts for n in cut}
|
||
|
|
H = G.subgraph(nodes)
|
||
|
|
for cc in nx.connected_components(H):
|
||
|
|
component = set(cc)
|
||
|
|
for cut in cuts:
|
||
|
|
for node in cut:
|
||
|
|
if has_nbrs_in_partition(G, node, cc):
|
||
|
|
component.add(node)
|
||
|
|
if len(component) < G.order():
|
||
|
|
components.append(component)
|
||
|
|
yield from _consolidate(components, k + 1)
|
||
|
|
|
||
|
|
|
||
|
|
def _reconstruct_k_components(k_comps):
|
||
|
|
result = dict()
|
||
|
|
max_k = max(k_comps)
|
||
|
|
for k in reversed(range(1, max_k + 1)):
|
||
|
|
if k == max_k:
|
||
|
|
result[k] = list(_consolidate(k_comps[k], k))
|
||
|
|
elif k not in k_comps:
|
||
|
|
result[k] = list(_consolidate(result[k + 1], k))
|
||
|
|
else:
|
||
|
|
nodes_at_k = set.union(*k_comps[k])
|
||
|
|
to_add = [c for c in result[k + 1] if any(n not in nodes_at_k for n in c)]
|
||
|
|
if to_add:
|
||
|
|
result[k] = list(_consolidate(k_comps[k] + to_add, k))
|
||
|
|
else:
|
||
|
|
result[k] = list(_consolidate(k_comps[k], k))
|
||
|
|
return result
|
||
|
|
|
||
|
|
|
||
|
|
def build_k_number_dict(kcomps):
|
||
|
|
result = {}
|
||
|
|
for k, comps in sorted(kcomps.items(), key=itemgetter(0)):
|
||
|
|
for comp in comps:
|
||
|
|
for node in comp:
|
||
|
|
result[node] = k
|
||
|
|
return result
|