 STAG Python Spectral Toolkit of Algorithms for Graphs
Searching...
No Matches
Getting Started

The STAG library is an easy-to-use Python library providing several spectral algorithms for graphs. The library is based on the STAG C++ library.

# Installation

Begin by installing STAG via pip, the python package manager.

pip install stag

# Creating Graphs

The core graph object is stag.graph.Graph which can be created using a sparse adjacency matrix.

import stag.graph
import scipy.sparse
adj_mat = scipy.sparse.csc_matrix([[0, 1, 1, 1],
[1, 0, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 0]])
The core object used to represent graphs for use with the library.
Definition: graph.py:287
Definition: graph.py:1

You can also create a variety of standard graphs using the stag.graph module. For example, to create a complete graph on $$5$$ vertices, use the following code.

import stag.graph
Graph complete_graph(n)
Construct a complete graph on n vertices.
Definition: graph.py:652

You can see the adjacency matrix of your constructed graphs with the followin code.

import scipy.sparse

Notice that the stag.graph.Graph.adjacency method returns a sparse scipy matrix and we make this dense with the todense() method.

STAG supports the edgelist file format for reading graphs from disk and the stag.graphio module provides methods for reading and writing them.

Suppose you have a simple edgelist file like this one.

0 1
1 2
0 2
2 3
3 4
4 5
3 5

Then, we can read it as follows.

>>> import stag.graphio
>>> print(g.agjacency().todense())
[[0. 1. 1. 0. 0. 0.]
[1. 0. 1. 0. 0. 0.]
[1. 1. 0. 1. 0. 0.]
[0. 0. 1. 0. 1. 1.]
[0. 0. 0. 1. 0. 1.]
[0. 0. 0. 1. 1. 0.]]
Definition: graphio.py:1
Load a graph from an edgelist file.
Definition: graphio.py:37

We can also save graphs as an edgelist.

import stag.graph
stag.graphio.save_edgelist(g, "star.edgelist")
Graph star_graph(n)
Construct a star graph.
Definition: graph.py:677
def save_edgelist(graph.Graph g, str filename)
Save a graph as an edgelist file.
Definition: graphio.py:47

Edgelist files can also include edge weights as a third parameter - notice that the generated star.edgelist file specifies an edge weight of $$1$$ for every edge.

0 1 1
0 2 1
0 3 1
0 4 1

See Graph File Formats for more information on the file formats supported by the STAG library.

# Finding Clusters

The stag.cluster module provides methods for finding clusters in graphs using local clustering algorithms. The main method provided by this module is stag.cluster.local_cluster. This method takes three arguments:

• g - a STAG graph object;
• seed_vertex - the ID of a vertex in the graph;
• target_volume - an estimate of the volume of the cluster to find. To estimate the target volume, you could first estimate the number of vertices in the cluster you would like to find, and then multiply by the degree of the seed vertex.

Given these arguments, stag.cluster.local_cluster will return a list of vertices which form a cluster around the seed vertex, and whose total volume is close to the target volume.

For example, to find the clusters in a barbell graph:

import stag.graph
cluster = stag.cluster.local_cluster(g, 0, 20)
print(cluster)
cluster = stag.cluster.local_cluster(g, 9, 20)
print(cluster)
Definition: cluster.py:1
List[int] local_cluster(graph.LocalGraph g, int seed_vertex, float target_volume)
Local clustering algorithm based on personalised Pagerank.
Definition: cluster.py:60
Graph barbell_graph(n)
Construct a barbell graph.
Definition: graph.py:665