Re: [igraph] Generate Cluster graph in C

[Tamas Nepusz]

> Hi, what i want to do is to create a graph like this:
>   - the graph is composed by many cluster (with diferent degree). All the 
> node in one cluster forms like a tree connected to tree (clusterheads).
>   - all the clusterheads are connected to one root (vertex 0 for example).
Try igraph_preference_game if you don't want to specify the cluster sizes 
exactly:

http://igraph.sourceforge.net/doc-0.5/html/igraph_preference_game.html

Imagine that you have 100 vertices and you want to make five clusters, each 
about the same size. This means that you need five vertex types, each vertex 
type occurring with a probability of 1/5. In the generated graph, you want 
vertices of the same type to be connected with probability p (where p is a 
reasonable probability between 0 and 1, it will control the "density" of the 
clusters), and you want vertices of different types to be connected with zero 
probability. So you'll probably need something like this (untested code, but it 
should show the general idea):

igraph_vector_t type_probabilities;
igraph_matrix_t attachment_probabilities;
igraph_vector_t vertex_types;
igraph_t graph;
int i;

/* Create the type probability vector */
igraph_vector_init(&type_probabilities, 5);
igraph_vector_fill(&type_probabilities, 0.2);

/* Create the attachment probability matrix */
igraph_matrix_init(&attachment_probabilities, 5, 5);
igraph_matrix_fill(&attachment_probabilities, 0);
for (i = 0; i < 5; i++) {
  MATRIX(attachment_probabilities, i, i) = 0.5;
}

/* Construct the graph and store the vertex types in vertex_types */
igraph_preference_game(&graph, 100, 5, &type_probabilities,
                       &attachment_probabilities, &vertex_types, 0, 0);

/* Destroy stuff that we don't need anymore */
igraph_vector_destroy(&type_probabilities);
igraph_matrix_destroy(&attachment_probabilities);


After this, the "graph" variable will contain a graph that has five separate 
components, and all pairs of vertices within the same component are connected 
with a probability of 0.5. All that you need now is to add an extra vertex and 
connect it to each of the components. This can be done by igraph_add_vertices 
and igraph_add_edges. To figure out which vertex belongs to which cluster, you 
can use the vertex_types vector that was prepared by igraph_preference_game.


The above approach won't work if you want to specify the sizes of the clusters 
_exactly_, as igraph_preference_game decides the vertex types by itself. In 
this case, you can generate five random graphs using igraph_erdos_renyi_game 
(these will be the separate components) and then add them together in a new 
graph using igraph_union or igraph_union_many. An example (not the most 
efficient):

igraph_t graph;
igraph_vector_ptr_t components;
int i, k = 5;

igraph_vector_ptr_init(&components, k);
for (i = 0; i < k; i++) {
  /* create the component */
  igraph_erdos_renyi_game(VECTOR(components)[i], IGRAPH_ERDOS_RENYI_GNP, 20, 
0.5, 0, 0);
}
/* unite all the components into a new graph */
igraph_union(&graph, &components);
/* destroy the original components, we don't need them anymore */
for (i = 0; i < k; i++) {
  igraph_destroy(VECTOR(components)[i]);
}

After this, you can use igraph_clusters to recover which vertex belongs to 
which cluster, then use igraph_add_vertices and igraph_add_edges to add the 
root vertex and its edges.

-- 
Tamas