igraph Reference Manual

For using the igraph C library

Search the manual:
Previous Home Next

Chapter 25. Graphlets

1. Introduction
2. Performing graphlet decomposition

1.  Introduction

Graphlet decomposition models a weighted undirected graph via the union of potentially overlapping dense social groups. This is done by a two-step algorithm. In the first step, a candidate set of groups (a candidate basis) is created by finding cliques in the thresholded input graph. In the second step, the graph is projected onto the candidate basis, resulting in a weight coefficient for each clique in the candidate basis.

For more information on graphlet decomposition, see Hossein Azari Soufiani and Edoardo M Airoldi: "Graphlet decomposition of a weighted network", https://arxiv.org/abs/1203.2821 and http://proceedings.mlr.press/v22/azari12/azari12.pdf

igraph contains three functions for performing the graphlet decomponsition of a graph. The first is igraph_graphlets(), which performs both steps of the method and returns a list of subgraphs with their corresponding weights. The other two functions correspond to the first and second steps of the algorithm, and they are useful if the user wishes to perform them individually: igraph_graphlets_candidate_basis() and igraph_graphlets_project().

Note: The term "graphlet" is used for several unrelated concepts in the literature. If you are looking to count induced subgraphs, see igraph_motifs_randesu() and igraph_subisomorphic_lad().

2. Performing graphlet decomposition

2.1. igraph_graphlets — Calculate graphlets basis and project the graph on it.
2.2. igraph_graphlets_candidate_basis — Calculate a candidate graphlets basis
2.3. igraph_graphlets_project — Project a graph on a graphlets basis.

2.1. igraph_graphlets — Calculate graphlets basis and project the graph on it.

igraph_error_t igraph_graphlets(const igraph_t *graph,
                     const igraph_vector_t *weights,
                     igraph_vector_int_list_t *cliques,
                     igraph_vector_t *Mu, igraph_integer_t niter);

This function simply calls igraph_graphlets_candidate_basis() and igraph_graphlets_project(), and then orders the graphlets according to decreasing weights.

Arguments: 

graph:

The input graph, it must be a simple graph, edge directions are ignored.

weights:

Weights of the edges, a vector.

cliques:

An initialized list of integer vectors. The graphlet basis is stored here. Each element of the list is an integer vector of vertex IDs, encoding a single basis subgraph.

Mu:

An initialized vector, the weights of the graphlets will be stored here.

niter:

The number of iterations to perform for the projection step.

Returns: 

Error code.

See also: igraph_graphlets_candidate_basis() and igraph_graphlets_project().

2.2. igraph_graphlets_candidate_basis — Calculate a candidate graphlets basis

igraph_error_t igraph_graphlets_candidate_basis(const igraph_t *graph,
                                     const igraph_vector_t *weights,
                                     igraph_vector_int_list_t *cliques,
                                     igraph_vector_t *thresholds);

Arguments: 

graph:

The input graph, it must be a simple graph, edge directions are ignored.

weights:

Weights of the edges, a vector.

cliques:

An initialized list of integer vectors. The graphlet basis is stored here. Each element of the list is an integer vector of vertex IDs, encoding a single basis subgraph.

thresholds:

An initialized vector, the (highest possible) weight thresholds for finding the basis subgraphs are stored here.

Returns: 

Error code.

See also: igraph_graphlets() and igraph_graphlets_project().

2.3. igraph_graphlets_project — Project a graph on a graphlets basis.

igraph_error_t igraph_graphlets_project(const igraph_t *graph,
                             const igraph_vector_t *weights,
                             const igraph_vector_int_list_t *cliques,
                             igraph_vector_t *Mu, igraph_bool_t startMu,
                             igraph_integer_t niter);

Note that the graph projected does not have to be the same that was used to calculate the graphlet basis, but it is assumed that it has the same number of vertices, and the vertex IDs of the two graphs match.

Arguments: 

graph:

The input graph, it must be a simple graph, edge directions are ignored.

weights:

Weights of the edges in the input graph, a vector.

cliques:

An initialized list of integer vectors. The graphlet basis is stored here. Each element of the list is an integer vector of vertex IDs, encoding a single basis subgraph.

Mu:

An initialized vector, the weights of the graphlets will be stored here. This vector is also used to initialize the the weight vector for the iterative algorithm, if the startMu argument is true.

startMu:

If true, then the supplied Mu vector is used as the starting point of the iteration. Otherwise a constant 1 vector is used.

niter:

The number of iterations to perform.

Returns: 

Error code.

See also: igraph_graphlets() and igraph_graphlets_candidate_basis().

← Chapter 24. Detecting community structure Chapter 26. Hierarchical random graphs →