For using the igraph C library
This section deals with functions which find small induced subgraphs in a graph. These were first defined for subgraphs of two and three vertices by Holland and Leinhardt, and named dyad census and triad census.
int igraph_dyad_census(const igraph_t *graph, igraph_integer_t *mut,
igraph_integer_t *asym, igraph_integer_t *null);
Dyad census means classifying each pair of vertices of a directed
graph into three categories: mutual, there is an edge from a to
b and also from b to a; asymmetric, there is an edge
either from a to b or from b to a but not the other way
and null, no edges between a and b.
Holland, P.W. and Leinhardt, S. (1970). A Method for Detecting Structure in Sociometric Data. American Journal of Sociology, 70, 492-513.
Arguments:
|
The input graph, a warning is given if undirected as the results are undefined for undirected graphs. |
|
Pointer to an integer, the number of mutual dyads is stored here. |
|
Pointer to an integer, the number of asymmetric dyads is stored here. |
|
Pointer to an integer, the number of null dyads is stored here. In case of an integer overflow (i.e. too many null dyads), -1 will be returned. |
Returns:
Error code. |
See also:
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
int igraph_triad_census(const igraph_t *graph, igraph_vector_t *res);
Calculating the triad census means classifying every triple of vertices in a directed graph. A triple can be in one of 16 states:
|
A, B, C, the empty graph. |
|
A->B, C, a graph with a single directed edge. |
|
A<->B, C, a graph with a mutual connection between two vertices. |
|
A<-B->C, the binary out-tree. |
|
A->B<-C, the binary in-tree. |
|
A->B->C, the directed line. |
|
A<->B<-C. |
|
A<->B->C. |
|
A->B<-C, A->C. |
|
A<-B<-C, A->C. |
|
A<->B<->C. |
|
A<-B->C, A<->C. |
|
A->B<-C, A<->C. |
|
A->B->C, A<->C. |
|
A->B<->C, A<->C. |
|
A<->B<->C, A<->C, the complete graph. |
See also Davis, J.A. and Leinhardt, S. (1972). The Structure of Positive Interpersonal Relations in Small Groups. In J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton Mifflin.
This function calls igraph_motifs_randesu() which is an
implementation of the FANMOD motif finder tool, see igraph_motifs_randesu() for details. Note that the order of the
triads is not the same for igraph_triad_census() and igraph_motifs_randesu().
Arguments:
|
The input graph. A warning is given for undirected graphs, as the result is undefined for those. |
|
Pointer to an initialized vector, the result is stored
here in the same order as given in the list above. Note that this
order is different than the one used by |
Returns:
Error code. |
See also:
Time complexity: TODO.
int igraph_adjacent_triangles(const igraph_t *graph,
igraph_vector_t *res,
const igraph_vs_t vids);
Arguments:
|
The input graph. Edge directions are ignored. |
|
Initiliazed vector, the results are stored here. |
|
The vertices to perform the calculation for. |
Returns:
Error mode. |
See also:
|
Time complexity: O(d^2 n), d is the average vertex degree of the queried vertices, n is their number.
int igraph_list_triangles(const igraph_t *graph,
igraph_vector_int_t *res);
Arguments:
|
The input graph, edge directions are ignored. |
|
Pointer to an initialized integer vector, the result is stored here, in a long list of triples of vertex ids. Each triple is a triangle in the graph. Each triangle is listed exactly once. |
Returns:
Error code. |
See also:
|
Time complexity: O(d^2 n), d is the average degree, n is the number of vertices.
igraph_motifs_randesu — Count the number of motifs in a graphigraph_motifs_randesu_no — Count the total number of motifs in a graphigraph_motifs_randesu_estimate — Estimate the total number of motifs in a graphigraph_motifs_randesu_callback — Finds motifs in a graph and calls a function for each of themigraph_motifs_handler_t — Callback type for igraph_motifs_randesu_callback
int igraph_motifs_randesu(const igraph_t *graph, igraph_vector_t *hist,
int size, const igraph_vector_t *cut_prob);
Motifs are small connected subgraphs of a given structure in a graph. It is argued that the motif profile (i.e. the number of different motifs in the graph) is characteristic for different types of networks and network function is related to the motifs in the graph.
This function is able to find the different motifs of size three and four (i.e. the number of different subgraphs with three and four vertices) in the network.
In a big network the total number of motifs can be very large, so
it takes a lot of time to find all of them, a sampling method can
be used. This function is capable of doing sampling via the
cut_prob argument. This argument gives the probability that
a branch of the motif search tree will not be explored. See
S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif
detection, Bioinformatics 22(9), 1152--1153, 2006 for details.
Set the cut_prob argument to a zero vector for finding all
motifs.
Directed motifs will be counted in directed graphs and undirected motifs in undirected graphs.
Arguments:
|
The graph to find the motifs in. |
|
The result of the computation, it gives the number of
motifs found for each isomorphism class. See
|
|
The size of the motifs to search for. Only three and four are implemented currently. The limitation is not in the motif finding code, but the graph isomorphism code. |
|
Vector of probabilities for cutting the search tree
at a given level. The first element is the first level, etc.
Supply all zeros here (of length |
Returns:
Error code. |
See also:
|
Time complexity: TODO.
Example 19.1. File examples/simple/igraph_motifs_randesu.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> void print_vector(igraph_vector_t *v) { long int i, n = igraph_vector_size(v); igraph_real_t sum = 0.0; for (i = 0; i < n; i++) { if (!igraph_is_nan(VECTOR(*v)[i])) { sum += VECTOR(*v)[i]; } } for (i = 0; i < n; i++) { igraph_real_printf(VECTOR(*v)[i] / sum); printf(" "); } printf("\n"); } igraph_bool_t print_motif(const igraph_t *graph, igraph_vector_t *vids, int isoclass, void* extra) { printf("Class %d: ", isoclass); igraph_vector_print(vids); return 0; } int main() { igraph_t g; igraph_vector_t hist; igraph_vector_t cp; igraph_vector_init_real(&cp, 8, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0); igraph_ring(&g, 1000, IGRAPH_DIRECTED, 1, 1); igraph_vector_init(&hist, 0); igraph_motifs_randesu(&g, &hist, 3, &cp); print_vector(&hist); igraph_destroy(&g); igraph_vector_destroy(&hist); igraph_famous(&g, "bull"); igraph_motifs_randesu_callback(&g, 3, &cp, &print_motif, 0); igraph_motifs_randesu_callback(&g, 4, &cp, &print_motif, 0); igraph_destroy(&g); igraph_vector_destroy(&cp); return 0; }
int igraph_motifs_randesu_no(const igraph_t *graph, igraph_integer_t *no,
int size, const igraph_vector_t *cut_prob);
This function counts the total number of motifs in a graph, i.e. the number of of (weakly) connected triplets or quadruplets, without assigning isomorphism classes to them.
Arguments:
|
The graph object to study. |
|
Pointer to an integer type, the result will be stored here. |
|
The size of the motifs to count. |
|
Vector giving the probabilities that a branch of the search tree will be cut at a given level. |
Returns:
Error code. |
See also:
Time complexity: TODO.
int igraph_motifs_randesu_estimate(const igraph_t *graph, igraph_integer_t *est,
int size, const igraph_vector_t *cut_prob,
igraph_integer_t sample_size,
const igraph_vector_t *parsample);
This function is useful for large graphs for which it is not feasible to count all the different motifs, because there is very many of them.
The total number of motifs is estimated by taking a sample of
vertices and counts all motifs in which these vertices are
included. (There is also a cut_prob parameter which gives the
probabilities to cut a branch of the search tree.)
Directed motifs will be counted in directed graphs and undirected motifs in undirected graphs.
Arguments:
|
The graph object to study. |
|
Pointer to an integer type, the result will be stored here. |
|
The size of the motif to look for. |
|
Vector giving the probabilities to cut a branch of
the search tree and omit counting the motifs in that branch.
It contains a probability for each level. Supply |
|
The number of vertices to use as the
sample. This parameter is only used if the |
|
Either pointer to an initialized vector or a null
pointer. If a vector then the vertex ids in the vector are
used as a sample. If a null pointer then the |
Returns:
Error code. |
See also:
Time complexity: TODO.
int igraph_motifs_randesu_callback(const igraph_t *graph, int size,
const igraph_vector_t *cut_prob, igraph_motifs_handler_t *callback,
void* extra);
Similarly to igraph_motifs_randesu(), this function is able to find the
different motifs of size three and four (i.e. the number of different
subgraphs with three and four vertices) in the network. However, instead of
counting them, the function will call a callback function for each motif
found to allow further tests or post-processing.
The cut_prob argument also allows sampling the motifs, just like for
igraph_motifs_randesu(). Set the cut_prob argument to a zero vector
for finding all motifs.
Arguments:
|
The graph to find the motifs in. |
|
The size of the motifs to search for. Only three and four are implemented currently. The limitation is not in the motif finding code, but the graph isomorphism code. |
|
Vector of probabilities for cutting the search tree
at a given level. The first element is the first level, etc.
Supply all zeros here (of length |
|
A pointer to a function of type |
|
Extra argument to pass to the callback function. |
Returns:
Error code. |
Time complexity: TODO.
Example 19.2. File examples/simple/igraph_motifs_randesu.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> void print_vector(igraph_vector_t *v) { long int i, n = igraph_vector_size(v); igraph_real_t sum = 0.0; for (i = 0; i < n; i++) { if (!igraph_is_nan(VECTOR(*v)[i])) { sum += VECTOR(*v)[i]; } } for (i = 0; i < n; i++) { igraph_real_printf(VECTOR(*v)[i] / sum); printf(" "); } printf("\n"); } igraph_bool_t print_motif(const igraph_t *graph, igraph_vector_t *vids, int isoclass, void* extra) { printf("Class %d: ", isoclass); igraph_vector_print(vids); return 0; } int main() { igraph_t g; igraph_vector_t hist; igraph_vector_t cp; igraph_vector_init_real(&cp, 8, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0); igraph_ring(&g, 1000, IGRAPH_DIRECTED, 1, 1); igraph_vector_init(&hist, 0); igraph_motifs_randesu(&g, &hist, 3, &cp); print_vector(&hist); igraph_destroy(&g); igraph_vector_destroy(&hist); igraph_famous(&g, "bull"); igraph_motifs_randesu_callback(&g, 3, &cp, &print_motif, 0); igraph_motifs_randesu_callback(&g, 4, &cp, &print_motif, 0); igraph_destroy(&g); igraph_vector_destroy(&cp); return 0; }
typedef igraph_bool_t igraph_motifs_handler_t(const igraph_t *graph,
igraph_vector_t *vids,
int isoclass,
void* extra);
igraph_motifs_randesu_callback() calls a specified callback
function whenever a new motif is found during a motif search. This
callback function must be of type igraph_motifs_handler_t. It has
the following arguments:
Arguments:
|
The graph that that algorithm is working on. Of course this must not be modified. |
|
The IDs of the vertices in the motif that has just been found. This vector is owned by the motif search algorithm, so do not modify or destroy it; make a copy of it if you need it later. |
|
The isomorphism class of the motif that has just been
found. Use |
|
The extra argument that was passed to |
Returns:
A logical value, if TRUE (=non-zero), that is interpreted as a request to stop the motif search and return to the caller. |
See also:
| ← Chapter 18. Graph Coloring | Chapter 20. Generating Layouts for Graph Drawing → |