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 ^[2]

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

References:
[1] Wikipedia: Independent set (graph theory)
[2] Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.