greedy_node_swap_bipartition

greedy_node_swap_bipartition(G, *, init_split=None, max_iter=10)

Split the nodes into two communities based on greedy modularity maximization.

The algorithm works by selecting a node to change communities which will maximize the modularity. The swap is made and the community structure with the highest modularity is kept.

Parameters:

GNetworkX graph

init_split2-tuple of sets of nodes

Pair of sets of nodes in G providing an initial bipartition for the algorithm. If not specified, a random balanced partition is used. If this pair of sets is not a partition of the nodes of G, NetworkXException is raised.

max_iterint

Maximum number of iterations of attempting swaps to find an improvement.

Returns:

max_split2-tuple of sets of nodes

Pair of sets of nodes of G, partitioned according to a node swap greedy modularity maximization algorithm.

Raises:

NetworkXError

if init_split is not a valid partition of the graph into two communities or if G is a MultiGraph

Notes

This function is not implemented for multigraphs.

References

[1]

M. E. J. Newman “Networks: An Introduction”, pages 373–375. Oxford University Press 2011.

Examples

>>> G = nx.barbell_graph(3, 0)
>>> left, right = nx.community.greedy_node_swap_bipartition(G)
>>> # Sort the communities so the nodes appear in increasing order.
>>> left, right = sorted([sorted(left), sorted(right)])
>>> sorted(left)
[0, 1, 2]
>>> sorted(right)
[3, 4, 5]