Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given four types of triads (figure below) their probabilities in a random Bernoulli digraph are as follows:

  • $T_{003}$: $(1-p)^6$
  • $T_{012}$: $6p(1-p)^5$
  • $T_{102}$: $3p^2(1-p)^4$
  • $T_{111D}$: $6p^3(1-p)^3$

For example, for triad $T_{012}$ there are six realizations of the asymmetric dyad and for triad $T_{102}$ there are three realizations of the mutual dyad.

Figure 1

My question is how to properly express the number of realizations of each triad type.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

If you have, for example, a large random Bernoulli digraph $G$ and are looking for the number of "copies" of a subgraph $H$, we can write something along the lines:

"...the number of induced subgraphs of $G$ isomorphic to $H$ is...".

This is the typical definition in the network motif literature (which seems to be the modern spin on dyads, triads, etc.). Variations on this theme are not unheard of (e.g. to account for the fact that the above definition counts overlapping "copies" of $H$ separately).

Note the word "induced", which is frequently (and, from a graph theory perspective, erroneously) omitted from many publications in this area. For example, the subgraph labelled "003" would occur exactly ${n \choose 3}$ times as a subgraph in any $n$-node network, whereas, it would likely occur fewer times as an induced subgraph.

Note: it's also fairly normal (at least in graph theory) to call these random graphs, Erdős-Rényi random graphs, since they are generated in the same spirit as the undirected model. This terminology is used, for example, in:

B. Bollobás, O. Riordan, Mathematical results on scale-free random graphs, in Handbook of graphs and networks, 2002.

Here's the default reference when using Erdős-Rényi random graphs:

P. Erdos, A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci, Vol. 5 (1960), pp. 17-61.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.