For using the igraph C library
Graphlet decomposition models a weighted undirected graph via the union of potentially overlapping dense social groups. This is done by a twostep algorithm. In the first step a candidate set of groups (a candidate basis) is created by finding cliques if the thresholded input graph. In the second step these the graph is projected on the candidate basis, resulting a weight coefficient for each clique in the candidate basis.
igraph contains three functions for performing the graph
decomponsition of a graph. The first is igraph_graphlets()
, which
performed both steps on the method and returns a list of subgraphs,
with their corresponding weights. The second and third 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()
.
int igraph_graphlets(const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_ptr_t *cliques, igraph_vector_t *Mu, int niter);
This function simply calls igraph_graphlets_candidate_basis()
and igraph_graphlets_project()
, and then orders the graphlets
according to decreasing weights.
Arguments:

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

Weights of the edges, a vector. 

An initialized vector of pointers. The graphlet basis is stored here. Each element of the pointer vector will be a vector of vertex ids. 

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

Integer scalar, the number of iterations to perform for the projection step. 
Returns:
Error code. 
See also: igraph_graphlets_candidate_basis()
and
igraph_graphlets_project()
.
int igraph_graphlets_candidate_basis(const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_ptr_t *cliques, igraph_vector_t *thresholds);
Arguments:

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

Weights of the edges, a vector. 

An initialized vector of pointers. The graphlet basis is stored here. Each element of the pointer vector will be a vector of vertex ids. 

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()
.
int igraph_graphlets_project(const igraph_t *graph, const igraph_vector_t *weights, const igraph_vector_ptr_t *cliques, igraph_vector_t *Mu, igraph_bool_t startMu, int 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:

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

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

The graphlet basis, a pointer vector, in which each element is a vector of vertex ids. 

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


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

Integer scalar, the number of iterations to perform. 
Returns:
Error code. 
See also: igraph_graphlets()
and
igraph_graphlets_candidate_basis()
.
← Chapter 22. Detecting Community Structure  Chapter 24. Hierarchical random graphs → 