Probabilistic Analysis of Graphlet Frequency Distribution in Sparse E-R Random Graphs

Abstract

Frequency counting of graphlets (i.e. small connected induced subgraphs) is a prominent experimental approach to network analysis which became favorable in bioinformatics. In this paper, we use the probabilistic method for graphlets counting. We show that it is possible to enumerate the graphlets (or isolated graphlets) in sparse Erdo˝s-Rényi graph model analytically. Obtained frequencies are exploited to estimate bounds on domination number in the above mentioned random graph model.

1 Introduction

Network science which is focused on modeling and analysis of real-world networks became a significant research area in last two decades. Instances of networks under study come from many fields of human activities, e.g. electrical engineering, transportation, social science, biology, medicine, etc. Currently, a frequently used algorithmic-experimental method for similarity detection and comparison of protein-protein interaction networks (shortly PPI networks) was invented in bioinformatics by N. Pržulj et al. [ 16 ]. It is based on frequency analysis of small connected induced subgraphs (called graphlets) occurring in networks to be compared. Such an approach was used to show e.g., that yeast PPI networks are structurally closer to geometric random graphs than to scalefree or Erdo˝s-Rényi random graphs [ 16 ].

Frequency counting of graphlets is a non-trivial algorithmic problem which is intensively studied both from theoretical and application point of view. One of the most powerful softwares used for this purpose is currently the Orbit Counting Algorithm - ORCA [ 8, 9 ]. Roughly speaking, ORCA writes numbers of all graphlets (with 2 − 5 nodes) which occurred in a given input network on output. This part of the graphlet-based analysis is the most difficult since doing it without a computer program is unrealistic even for relatively small networks. Due to high computational complexity of the graphlet enumeration the number of their nodes is restricted to at most 4 in some current softwares.

In this paper, we show that the problem of frequency counting of graphlets can be solved analytically in Erdo˝sRényi random graph model by probabilistic methods. Some previous results regarding random graph theory [ 1, 3, 10, 11, 17 ] are relied on this purpose. Our result is significant especially from the complexity point of view because it might lead, in some cases, to elimination of high requirements on computational resources needed for graphlet frequency analysis. It means that instead of computer-based graphlet frequency enumeration in Erd o˝sRényi random graphs one may use analytical formulas.

The organization of the paper is as follows. Sect. 2 contains definitions and preliminary facts. The threshold functions for presence of graphlets in random graphs are derived in Sect. 3. Average counts of graphlets are expressed in the same section as well. Average counts of isolated graphlets and corresponding estimations in random graphs with edge probability p = c/n are determined in Sect. 4. Application of these results to estimation of the domination number in sparse random graphs is outlined in Sect. 5. Possible direction for future research are discussed in the last section. 2 2.1

Definitions and Preliminaries

Fundamentals

The asymptotic notation such as o, O, Θ is used in the usual way [ 10 ], nevertheless, the most important notions are listed below.

O(g(n)) = { f (n) | ∃ c, n0 > 0 ∀n ≥ n0 | f (n)| ≤ c| g(n)| } Ω (g(n)) = { f (n) | ∃ c, n0 > 0 ∀n ≥ n0 | f (n)| ≥ c| g(n)| } o(g(n)) = { f (n) | ∀ ε > 0 ∃n0 > 0 ∀n ≥ n0 | f (n)| ≤ ε | g(n)|} f (n) = Θ(g(n))) ⇔ f (n) = O(g(n)) ∧ f (n) = Ω (g(n)) Moreover, for two sequences (or equivalently functions) a = (an)n=0 and b = (bn)n∞=0, we will write an ≪ bn if ∞ an ≥ 0 and an = o(bn).

Throughout this paper, all graphs are simple, undirected and without weights. Standard notions of the graph theory are used without definitions or further comments. We address [ 6, 7 ] for references however, the usage of some symbols is mentioned bellow. Let G = (V, E) be a graph with a nonempty finite set of vertices V (G) (or nodes) and a finite set of edges E(G). Usually | V (G)| = n, where | .| stands for the cardinality of a given set. For a vertex v ∈ V (G), its degree (the number of adjacent vertices of v) is denoted by deg(v). The maximum (minimum) degree of a graph G is denoted by ∆ (δ ). Let G = (V, E) be a graph and let S ⊆ V (G), an induced subgraph G[S] is the graph whose vertex set is S and the edge set of G[S] consists of all edges whose endpoints are both in S. A graph is said to be connected if there is a path joining every pair of its vertices. A disconnected graph is not connected. A component is a maximal connected subgraph. It is also referred to as connected component or isolated component. Note that each disconnected graph consists of at least two different components.

Let G = (V, E) be a graph, a graphlet is a connected induced subgraph of G with at most 5 vertices. Two graphlets are same if there exists an isomorphism such that it maps one graphlet to the other one. (Two different occurrences of the same graphlet are usually referred to as its copies.) In this paper, only graphlets with at most 4 vertices are considered. Their ordering (and indexing) is shown in Fig. 1. It means that the empty graph (a single vertex) is denoted by g0, etc. The last graphlet in Fig. 1 (i.e. g9) is the clique K4. 2.2

Random Graphs

The Erdo˝s-Rényi random graph model (shortly E-R model) [ 3 ] can be introduced as follows.

Let n be a positive integer and let p ∈ IR be a constant such that 0 < p < 1. Consider that for n labeled vertices of V (G), each unordered pair of vertices introduces one slot available for an edge. Clearly, the total number of slots is ( n2) . Each edge exists in G independently and with the probability p, thus Pr[{ u, v} ∈ E(G)] = p, for all u, v ∈ V (G).

Given n as above, let (Ω , IF, Pr) be a probability space where the sample space Ω consists of all (labeled) graphs G of order n and let IF ⊆ 2Ω be a set of events. If G has | E(G)| edges, 0 ≤ | E(G)| ≤ ( n2) , then the probability of obtaining G as a result of random edge generation process is given by: n Pr[G] = p| E(G)| (1 − p)(2)−| E(G)| .

The probability space (Ω , IF, Pr) is denoted by G(n, p) or Gn,p and called the probability space of all random graphs of order n or E-R random graph model .

A statement about a random graph from G(n, p) is said to hold asymptotically almost surely (a.a.s.) if it holds with probability approaching 1 as n → ∞. A graph G with n vertices is said to be dense if it has Θ(n2) edges (i.e., asymptotically equal to n2) and G is said to be sparse if it has o(n2) edges (i.e., asymptotically less than n2).

If one considers p to be a non-zero constant, then random graphs have pn(n − 1)/2 = Θ(n2) edges, hence they are dense a.a.s. On the other hand, there are such choices of p that random graphs are sparse. E.g. if p = p(n) is a decreasing function on n such as p = n−ε for any constant ε > 0 then random graphs have Θ(n2−ε ) edges and they are sparse a.a.s. In particular, if p = c/n = Θ(n−1) for any constant c > 0, then random graphs have a linear number of edges (observe that ε = 1, hence random graphs are sparse a.a.s.) and, in terms of edge set cardinality, they are similar to real-world networks. On the other hand, some structural properties of sparse random graphs are usually far from real-world networks [ 2, 16 ]. Many works deal with structural properties of real networks and quite realistic models are currently represented by e.g. scale-free or random geometric networks [ 2, 8, 16 ]. 2.3

Monotonicity and Threshold Functions

In physics, a phase transition is the transformation of a thermodynamic system from one phase to another. During such a transformation, some physical properties of the system change discontinuously. An example is freezing (or boiling) water or the emergence of superconductivity in certain metals when cooled below the critical temperature. In all phase transitions, there exists a value of a certain quantity (often temperature) in which the physical properties in question change.1 Such a value is said to be a critical point.

Similar behavior was also observed in random graphs (for the first time in [ 3 ]). The critical points in thermodynamics have their counterparts in random graphs: they are thresholds functions. (1)

1The character of such a change is similar to a jump discontinuity function.

Let Kn be a clique with n > 0 vertices. Let 2Kn denote the power set of all spanning subgraphs of Kn. Let G1, G2 be spanning subgraphs of Kn and let G1 ⊆ G2 denote that E(G1) ⊆ E(G2). Let Q ⊆ 2Kn be a family of subsets and note that Q contains spanning subgraphs of Kn. A family of graphs Q is said to be increasing if G1 ⊆ G2 and G1 ∈ Q imply that G2 ∈ Q. A family of graphs Q′ is decreasing if 2Kn \ Q′ is increasing. A family which is either increasing or decreasing is called monotone. A family of graphs G is said to be closed under isomorphism if for all G ∈ G and H ∼= G implies that H ∈ G . If a family of graphs from 2Kn is closed under isomorphism, it can be identified with a graph property.

Threshold functions are usually defined for monotone properties. In this paper, we need to introduce them only for increasing properties. For further details see [ 10 ]. Let Q be an increasing property of graphs from 2Kn . Let p = p(n) be a function. A function pb = pb(n) is called a threshold function for Q iff the following condition holds: Pr[ G(n, p) has Q ] → {

Threshold functions play a crucial role in examination of the phase transition phenomena in random graphs [ 3, 10, 11, 15 ]. A typical property is the connectivity of random graphs and more specifically, size of connected components. The threshold function for the existence of a giant component is p = 1/n. As stated in [ 15 ], Sect. 4, a b random graph contains a.a.s. the largest component with Θ(n2/3) vertices in its critical phase, i.e. if p = 1/n. The subcritical phase is for p = c/n where 0 < c < 1. It represents such a state that all components are trees or unicyclic and the largest component is of size Θ(log n) a.a.s. Otherwise, if p = c/n where c > 1, then there is a unique giant component of order Θ(n) a.a.s. in the supercritical phase. The rest of the random graph consists of "small" trees and as c increases, the giant component grows by absorbing the trees. 3

Graphlets

Let Xgi be the random variable on G(n, p) denoting the number of copies of graphlet gi in a random graph for i = 0, . . . , 9. In this paper, we consider 10 graphlets with at most 4 vertices (see Fig. 1) that is why i = 0, . . . , 9. Lemma 1 ([ 10 ]). For i = 0, . . . , 9, let ni (mi) denote the number of vertices (edges) of gi. The expectation of the random variable Xgi is given by

IE(Xgi ) =

ni! ( n ) aut(gi) ni

n pmi (1 − p)( 2i)−mi , (2) where aut(gi) denotes the number of automorphisms of gi.

Vertices (i.e. graphlets g0) represent a trivial case, thus we will consider only random variables Xgi for i > 0 in this section. We shall examine the phase transition behavior of graphlets at first. The occurrence of a given graphlet is not a monotone property [ 10 ]. Nevertheless, such a property has two threshold functions, one in sparse random graphs and the second in very dense random graphs [ 10 ]. We are interested only in the first case since almost all real networks are sparse.

For a given graph G, let τ (G) denote the ratio of the number of edges to the number of vertices in the densest subgraph of G, i.e.

τ (G) = max { | E(H)| ; H ⊆ G, | V (H)| > 0 | V (H)| }

The following statement determines threshold functions for graphlets.

Theorem 1 ([ 10 ]). For an arbitrary graphlet g with at least one edge, it holds lim Pr[ g occurs in G(n, p) ] = n→∞ { 0 if p ≪ n−1/τ (g) , 1 if p ≫ n−1/τ (g) .

As a consequence, we obtain Tab. 1 in which the thresholds functions for all nontrivial graphlets are listed. Determination of threshold functions is straightforward because none of graphlets (for i = 1, . . . , 9) contains a denser subgraph than itself. Clearly, τ (g1) = 1/2 and τ (g2) = τ (P3) = 2/3. By the same argument, τ (g3) = τ (△) = 3/3 = 1, etc.

If we consider sparse random graphs with p = c/n, then it is possible to deduce from Tab. 1 which graphlets occur more or less frequently. We can see that the presence of trees (i.e. graphlets g1, g2, g4 and g5) is the most probable of all graphlets in G(n, c/n). On the other hand, dense graphlets (such as the clique g9) rarely occur in G(n, c/n).

The expected number (or "average counts") of graphlets can be derived from Lemma 1. The probabilities of graphlets and corresponding expectations of the random variable Xgi are listed in Tab. 2. The numbers of automorphisms aut(gi) for these small graphs are well-known (see [ 19 ] for the details). (3) Given a graph G = (V, E), a graphlet is said to be an isolated graphlet if it is a component in G. Let Ygi be the random variable on G(n, p) denoting the number of copies of isolated graphlet gi in a random graph for i = 0, . . . , 9. It will be seen later (in Tab. 3) that it is meaningful to take into account the isolated graphlet g0 as well.

Lemma 2 ([ 10 ]). For i = 0, . . . , 9, let ni (mi) denote the number of vertices (edges) of gi. The expectation of the random variable Ygi is given by

IE(Ygi ) = IE(Xgi ) · (1 − p)(n−ni)ni .

In order to express an asymptotic estimation for "average counts" of isolated graphlets in random graphs, the following lemma is necessary.

Lemma 3. Let α ,β , c be constants (i.e. α ,β , c ≪ n) such that α , c > 0 and let p = c/n. It holds (1 − p)α n+β ∼ e−α c as n → ∞ .

Proof. By assumptions of Lemma, (1 − p)α n+β = ( 1 − nc ) α n · ( 1 − nc ) β . (1 − p)α n+β = ( 1 +

n − c 1 ) −−αcnc ( c ) β · 1 − n ∼ e−α c Thus since and lim n→∞ ( 1 +

n 1 ) − c n − c

= e ( c ) β lim 1 − n n→∞

By Lemma 2 and 3, we derive the following statement. It determines the asymptotic estimation for expected number of isolated graphlets in random graphs with p = c/n. Lemma 4. Let c > 1 be constant. There exists a function ψc(n) = O(n−1) such that for each gi (with ni vertices and mi edges) in G(n, c/n) it holds

IE(Ygi ) ∼  ncni−1e−cni /aut(gi) if mi = ni − 1,      cni e−cni /aut(gi) if mi = ni,     ψc(n) if mi ≥ ni + 1.

This lemma allows for asymptotic estimation of expected numbers of isolated graphlets in random graphs G(n, c/n). Corresponding estimations are listed in Tab. 3. One may observe that the frequency of isolated trees (i.e. graphlets g0, g1, g2, g4, g5) growth linearly with n, the frequency of isolated graphlets g3, g6, g7 (i.e. trees with one additional edge) is constant with respect to n and the frequency of other isolated graphlets (g8 and g9) is negligible. The intuition behind this result is, similarly as in the previous section, that the contribution of sparse isolated graphlets is more significant (even in magnitude) than of denser ones. Unless as in the previous section, the frequency distribution of isolated vertices g0 can be expressed by the asymptotic formula which depends on n and c. (Note that the count of graphlets g0 is trivially n.) Graphlet gi g0 g1 g2 g3 g4 g5 g6 g7 g8 g9

IE(Ygi ) n(1 − p)n−1 ( n) p(1 − p)2(n−2) 2 3! ( n) p2(1 − p)3(n−3)+1 2 3 3! ( n) p3(1 − p)3(n−3) 6 3 4! ( n) p3(1 − p)4(n−4)+3 2 4 4! ( n4) p3(1 − p)4(n−4)+3 6 4! ( n4) p4(1 − p)4(n−4)+2 8 4! ( n4) p4(1 − p)4(n−4)+2 2 4! ( n) p5(1 − p)4(n−4)+1 4 4 244! ( 4n) p6(1 − p)4(n−4)

Estimation of

IE(Ygi ) for p = c/n

ne−c 12 nce−2c 12 nc2e−3c 1 c3e−3c 6 12 nc3e−4c 16 nc3e−4c 1 c4e−4c 8 1 c4e−4c 2 14 n−1c5e−4c 214 n−2c6e−4c 5

Domination Number in Sparse Random

Graphs

A dominating set of a graph G = (V, E) is a set D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex of D. The domination number, denoted by γ (G), is the minimum cardinality of a dominating set of G.

Results regarding domination problems and domination number are surveyed in [ 7 ]. Due to significant applications in social, engineering and PPI networks, the area of domination became recently attractive and fast growing [ 5, 12, 13, 14, 18 ].

It was shown in [ 18 ] that the domination number of random graphs for a constant p may attain one of only two possible values. Such a property is called the two-point concentration. The two-point concentration result was recently extended for random graphs G(n, p) with p ≫ l√n2nn (in this case, p = p(n) is assumed to be a function). However, it does not hold if p = O(log n/n) [ 5 ]. As mentioned in [ 5 ], the detailed analysis of the domination number behavior for random graphs with p ≪ √1n is still an interesting open problem.

In order to pursuit this problem, we suggest to use a method based on isolated graphlet counting. Recall that a random graph consists of a single giant component and small isolated trees a.a.s. in its critical and supercritical phase if p = Θ(n−1). Roughly speaking, our idea resides in exact counting of domination numbers for isolated trees and its estimation for the giant component. Resulting bounds could be obtained by a combination of all particular estimations. Our preliminary results exploiting the early version of this idea have been published in [ 14 ]. 6

Concluding Remarks

One possible extension of this work may involve analysis for graphlets with 5 vertices. Although the idea is the same as for smaller graphlets, detailed calculations need an additional effort because there are 21 graphlets with 5 vertices.

Comparing actual networks to random graphs might be a meaningful goal for future research. A resulting knowledge might be helpful to better understanding of realworld networks structure.

As regards the problem of the domination number estimation, the author is currently working on more accurate formulas of results published in [ 14 ]. The corresponding analysis is based on the idea which was explained in the previous section.

Acknowledgement. The support from the Slovak Scientific Grant Agency under the grant VEGA 1/0026/16 is gratefully acknowledged.

The author thanks the anonymous referees for their valuable comments on the manuscript.

References

[1] B. Bollobás : Random Graphs. (2nd edition) Cambridge Studies in Advanced Mathematics 73 , ( 2001 )

[2] J. Dreier , P. Kuinke , B. Le Xuan , P. Rossmanith: Local Structure Theorems for Erdo˝s-Rényi Graphs and Their Algorithmic Applications . In Proc. of the 44th Int. Conference on Current Trends in Theory and Practice of Comp. Science, SOFSEM 2018 , LNCS 10706, Springer Int. Publishing, 2018 , 125 - 136

[3] P. Erdo ˝s, A. Rényi: On the evolution of random graphs . Publ. Math. Inst. Hungar. Acad. Sci. 5 ( 1960 ) 17 - 61

[4] M. R. Garey , D. S. Johnson: Computers and Intractability. Freeman, New York ( 1979 )

[5] R. Glebov , A. Liebenau , T. Szabó: On the Concentration of the Domination Number of the Random Graph . SIAM J. Discrete Math., 29:3 ( 2015 ) 1186 - 1206

[6] J.L. Gross , J. Yellen: Handbook of Graph Theory . CRC Press ( 2003 )

[7] T. W. Haynes , S. T. Hedetniemi , P. J. Slater : Fundamentals of Domination in Graphs . Marcel Dekker, Inc., New York ( 1998 )

[8] T. Hocˇevar: Graphlet Counting . In Proc. of the 17th Conference on Applied Mathematics, APLIMAT 2018 , SUT in Bratislava, 2018 , 442 - 449

[9] T. Hocˇevar , J. Demšar: Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs . Journal of Statistical Software 71 : 10 ( 2016 )

[10] S. Janson , T. Łuczak , A. Rucinski: Random Graphs . John Wiley & Sons, New York ( 2000 )

[11] M. Karon ´ski: Random Graphs . Handbook of Combinatorics (R.L. Graham , M. Grötschel , L. Lovász eds. ) , Vol I , Elsevier, 1995 , 351 - 380

[12] F. Molnár , S. Sreenivasan , B. K. Szymanski , G. Korniss: Minimum Dominating Sets in Scale-Free Network Ensembles . Scientific Reports 3 , Article number : 1736 ( 2013 )

[13] J. C. Nacher , T. Akutsu: Dominating scale-free networks with variable scaling exponent: heterogeneous networks are not difficult to control . New Journal of Physics 14 , 073005 ( 2012 )

[14] M. Nehéz , D. Bernát , M. Lelovský: Estimation of the domination number in sparse random graphs and applications . In Proc. of the 5th European Conference on the Engineering of Computer-Based Systems, ECBS 2017 , ACM New York, 2017 , 7 : 1 - 7 : 9

[15] E. M. Palmer: Graphical Evolution . John Wiley & Sons, Inc., New York ( 1985 )

[16] N. Przulj , D.G. Corneil , I. Jurisica: Modeling interactome: scale-free or geometric? . Bioinformatics 20 :18 ( 2004 ) 3508 - 3515

[17] A. Rucinski : Small subgraphs of random graphs. Presentation of the talk , Joint Mathematics Meeting #1003 , MAA 2005 , Atlanta ( 2005 ) URL: https://www.math.cmu.edu/ãf1p/MAA2005/L4.pdf

[18] B. Wieland , A.P. Godbole : On the Domination Number of a Random Graph . Electronic Journal of Combinatorics 8 : 1 ( 2001 ) # R37

[19] Wolfram MathWorld : Graph Automorphism. URL: http: //mathworld.wolfram.com/GraphAutomorphism.html ( 2018 )