Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Question

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of:

1.self-edges
2.feed-forward loops [example][1]
3.feed-back loops [example 2][2]

Sorry I'm quite new to the field.. I presume that for 1. the probability for a node to connect to itself is 1/N* ...so the expected number of self-edges would be E/N*, where E is the number of edges in a random network. What about 2 and 3? Can someone show me the logic?

Answer 1

I found the answer through biology and posted it here as well: Answer

1. The average number of self-edges, is equal to the number of edges E times the probability that an edge is a self-edge which is $p_{self}=1/N$, with N being the total number of nodes. Therefore, $<N_{self}>_{rand} \approx E/N$
2. & 3. According to U.Alon's book ("Introduction to Systems Biology"), the mean number of times that a subgraph G occurs in a random network is given by the following formula: $<N_G>\approx a^{-1}N^n p^g$.

Explaining what each term of the formula means:

• α: is a number that includes combinatorial factors related to the structure and symmetry of each subgraph, equal to 1 for feed-forward loop (FFL) and equal to 3 for feed-back loop (FBL)
• $N^n$: is the number of ways of choosing a set of n nodes out of N. Because there are N ways of choosing the first one, times N-1$\approx$N ways of choosing the second one, and so on..(this approximation is true for large networks)
• $p^g$ : is the probability to get the g edges in the appropriate places (each with probability p)