This article presents how to calculate a maximal independent set with the Python package, NetworkX.
1. Independent set
Excerpt from Wikipedia: Independent set (graph theory)：
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets.
A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, and denoted α(G). The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
maximal vs maximum
Before calculating an independent set, we should clarify the differences between a maximal independent set and a maximum independent set. A ‘maximal’ independent set, is an independent set where if you add any other vertex, it will not be an independent set anymore. This is different from a ‘maximum’ independent set, which is the biggest possible independent set belonging to the graph. While ‘maximum’ is usually used in optimization terms, ‘maximal’ is the property of one particular answer to a question.
1.1. An example
NetworkX provides two interfaces to calculate an approximate maximum independent set.
nx.maximal_independent_set(G, nodes=None), returns a random maximal independent set guaranteed to contain a given set of nodes.
nxaa.maximum_independent_set(G), returns an approximate maximum independent set 
As an example, we calculate an independent set on Florentine families graph using
nx.maximal_independent_set(G, nodes=None). (PS: the complete source code is hosted on my GitHub, here).
import networkx as nx import networkx.algorithms.approximation as nxaa # build up a graph filename = '../../florentine_families_graph.gpickle' G = nx.read_gpickle(filename) # Independent set maximal_iset = nx.maximal_independent_set(G)
As shown below, the independent set is highlighted in red.
Fig. 1: An independent set in Florentine families graph (in red)
2. The source code
The source code of
nx.maximal_independent_set is available here. To make it easier to follow, I put some comments on it.
import random import networkx as nx def maximal_independent_set(G, nodes=None): if not nodes: nodes = set([random.choice(G.nodes())]) # pick a random node else: nodes = set(nodes) if not nodes.issubset(G): raise nx.NetworkXUnfeasible("%s is not a subset of the nodes of G" % nodes) # All neighbors of nodes neighbors = set.union(*[set(G.neighbors(v)) for v in nodes]) if set.intersection(neighbors, nodes): raise nx.NetworkXUnfeasible("%s is not an independent set of G" % nodes) indep_nodes = list(nodes) # initial available_nodes = set(G.nodes()).difference(neighbors.union(nodes)) # available_nodes = all nodes - (nodes + nodes' neighbors) while available_nodes: # pick a random node from the available nodes node = random.choice(list(available_nodes)) indep_nodes.append(node) available_nodes.difference_update(G.neighbors(node) + [node]) # available_nodes = available_nodes - (node + node's neighbors) return indep_nodes
 Wikipedia: Independent set (graph theory)
 Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.
One thought on “Calculate a maximal independent set with Python”