Re: [igraph] Random graph based on probabilities derived from sample graph

[Tamas Nepusz]

Hi,

> I guess then that I should be able to define a probability model based on
> four type of events for each pair of people:
> 1) p of "No relationship";
> 2) p of "A -> B";
> 3) p of "A <- B";
> 4) p of "A <-> B".
> Is that right?
#2 and #3 should be equal, shouldn't it? (Unless there is some constraint on
A and B, e.g., that A < B)

> How should I compute the model from my graph? Is there any
> function I should use?
No; igraph doesn't have any predefined graph models that would work for you.
You have to construct the edge list "manually" and then pass it to an
appropriate graph constructor.

When constructing the edge list, you can probably use the following method. We
will first generate the "A -> B" edges where the index of A is less than the
index of B. Then we randomly select a fraction of these edges and create them
in the opposite direction as well.

To generate the "A -> B" edges, first note that there exists a mapping from the
cells of the upper triangle of an arbitrary adjacency matrix into a range of
integers as follows (I use 1-based indexing here; imagine that they are 0-based
if you use igraph from C or Python):

(1, 2) --> 1
(1, 3) --> 2
(1, 4) --> 3
...
(1, N) --> N
(2, 3) --> N+1
(2, 4) --> N+2
...
(2, N) --> 2N-1
(3, 4) --> 2N
(3, 5) --> 2N+1
...
(3, N) --> 3N-2
...
(N-1, N) --> N^2-N-1

I guess you get the idea. Now, we simply take a random sample without
replacement from the range [1; N^2-N-1] such that each item is sampled with
some probability p (which you can calculate from your original graph). Then we
map these indices back to adjacency matrix cells (using the inverse of the
mapping above; the best is if you create a separate function for both
directions of the mapping). This way we have obtained the set of "forward"
(i.e. A --> B) edges. We can then take a random sample of the "forward" edges
without replacement, again with some probability p2 (which you can calculate
from your original graph) to obtain the set of "reverse" edges. The final graph
will be the concatenation of these two edge lists.

Note that the above method is "biased" in the sense that there are always more
edges for which the index of the source is less than the index of the target,
but I assume here that you do not care about the exact ordering of nodes.

-- 
T.