Continuous-Time Independent Edge-Markovian Random Graph Process∗

Ruijie DUHanxing WANGYunbin FU

1 Introduction

In the study of complex networks(see[1–2]),network evolution is usually described by the evolution of graphs(see[3–5]).Graph evolution includes adding vertices,adding edges,deleting vertices,deleting edges,and reconnecting.Reconnection is to consider the connection of edges on the assumption that the number of vertices remains unchanged.Researchers often use the Markov process to describe the edge reconnection,and discuss the random graph process model based on the classic theory of Markov chains;this assumption is also consistent with the evolution characteristic of many actual networks.

Using the Markov process to describe the dynamic evolution of the network is an important research content of the random graph process,which has gained a lot of achievements.Han[6]assumed that the random graph process was a homogeneous Markov process;its state space was a simple directed graph set which had the same set of vertices.By adding or deleting an edge(probabilities of adding or deleting edges related to edge numbers of the graph),transfer of the state was achieved.Under this assumption,stationary distribution of the random graph sequences was studied;Chen Avin et al[7]proposed a general Markov dynamic graph model:The state space was a set composed of graphs which had the same set of vertices;they also discussed the encountering time and continuing time between the nodes of the model.Clementi et al[8]proposed a discrete Markov dynamic graph model based on edge-independent evolution,namely,probability of every state which disconnects(connected)in timetand connected(disconnects)in timet+1 wasp(n)(q(n)),wherenwas the number of nodes.Under the assumptions of this model,Clementi discussed the flooding time of such dynamic graphs.As a special case of[7],the edge-independent evolution Markov dynamic graph model was easier to handle mathematically.As the supplement of[8],Herv et al[9]proposed that the evolution graph de fined on the time sequences was mapped to a weighted random graph,which eliminated corrections of dynamic network evolution,and they also proved that the weighted graph had the same topological properties as the time evolution graph.In 2011,according to the highly dynamic topology and characteristics that are evaluated with time in the opportunity network,Cai et al[10]proposed the time evolution graph model based on edgeindependent evolution,and the model assumed that the edge evolution between any node pair was independent of the other node pairs.They used the discrete Markov chain and the birth and death process to characterize the evolution of time correlation and the Laplace successor rule to estimate the probability of the edge births and deaths,and then analyzed the convergence characteristics of the dynamic evolution network.Du[11]constructed a probability space and a random graph process:{Gt}t≥0,G0is anm-complete graph,andv0,v1,···,vm−1aremvertices of it.Du proved that this mathematical model has the same marginal distributions and boundary conditions as the BA model,and{Gt}t≥0can be considered as graph value Markov chains constructed on its probability space.

Unlike other researches on the discrete Markov dynamic graph model with independent edge-Markovian evolution,this article discusses the topology properties of the continuous-time Markov dynamic graph model with edge-independent evolution,and by using the independence of the chain process and Markov assumptions,we have explored the statistical properties of the distribution of the number of isolated nodes and the connection probability.

2 Distribution of the Number of Isolated Nodes

De finition 2.1(see[1])Suppose that(Ω,F,P)is a probability space,and{Gt(ω):t≥0}is an undirected random simple graph process de fined on(Ω,F,P),whereN≥2,t≥0,the corresponding adjacency matrix process is

If the chain processessatisfy the following conditions:

(1)chain processes are independent of each other,namely,independent of each other;

(2)Every chain process{ξij(t,ω):t≥0}is a continuous-time Markov chain which has two states0and1,and its density matrix is

where,thenis de fined as an independent edge-Markovian random graph process.

The transfer function of the chain processesis denoted asObviously,the independent edge-Markovian random graph process is a Markov random graph process having stationary distributionwhich is a symmetric matrix with{0,1}element.Then

whereπij(·)is the distribution on 0,1,

In the article below,unless specially described,we always assume that the chain processes have the same distributions,i.e.,each chain process has the same density matrix

Therefore,it has the same stationary distribution,namely,

If we choose the stationary distribution as its initial distribution,then the independent edge-Markovian random graph process is a stationary random graph process,namely,∀t≥0,i/=j,

That is to say,∀t≥0,Gtis such a random graph thatand for any two nodesiandj,their connection probability isp,disconnected probability isq,and whether it is connected or not every node pair is mutually independent.

Suppose that{Gt:t≥0}is a graph family,V(Gt)=V,t≥0.If nodei∈Vis an isolated node of allGs,t0≤s≤t,theniis de fined as the interval isolated node of the graph familyon[t0,t].

The interval isolated node is a concept associated with the evolution of the graph.If nodeiis the interval isolated node of the graph family{Gt:t≥0}on[t0,t],that is in the evolution process of the graph,nodeialways maintains the state of isolated nodes in the period[t0,t].

De finition 2.2(see[2])Suppose that{Gt(·):t≥0}is the independent edge-Markovian random graph process,where V(Gt)={1,2,···,N},N≥2,t≥0,and also suppose that the chain process is identically distributed,and its initial distribution is the stationary distribution,∀i∈V.Suppose further t≥0,

Then the random variable ηt(ω)is the number of isolated nodes of the random graph process{Gt(·):t≥0}at time t.

∀0≤t0＜t,i∈V,suppose

Then the random variableξ(ω;t0,t)is the number of interval isolated nodes of the random graph processon[t0,t].

Note that the random events{i(ω,t)=1}and{j(ω,t)=1},i/=jare not independent of each other,becauseSoηt(ω)does not obey binomial distribution.Similarly,the number of interval isolated nodesξ(ω;t0,t)does not obey binomial distribution either.

Lemma 2.1(see[3])Suppose that G(ω)is a random graph,and V(G(ω))={1,2,···,n},n≥2;the probability of its arbitrary two different nodes connected is p,and the probability of disconnected is q=1−p;and all node pairs,whether the nodes are connected or not,are independent of each other.Then the probability of G(ω)having no isolated nodes is

ProofSuppose thatAiis a random event,andiis an isolated node,i=1,2,···,n.Then in addition to the multi-less complement principle

we can get

This completes the proof.

Theorem 2.1Suppose that{Gt(·):t≥0}is an independent identically distribution edge-Markovian random graph process which has stationary distribution as its initial distribution,V(Gt)={1,2,···,N},N≥2,t≥0,and the density matrix of the chain process is

Then ηt(ω)is the number of isolated nodes of the random graph process{Gt(·):t≥0}at time t≥0,and its distribution is

where

Remark 2.1Obviously,(ηt(ω)=N−1)=(ηt(ω)=N).Therefore,

That is to say,the value ofηt(ω)is 0,1,2,···,N−1,or 0,1,2,···,N−2,N.

Proof of Theorem 2.1According to the assumptions,∀t≥0,Gt(ω)have the independent chains,and the probability of any two nodes connected iswhile the probability of disconnected isAccording to Lemma 2.1,

Suppose thatAiis a random event,iis an isolated node ofThen from Lemma 2.1 and the total probability formula for

where

This completes the proof.

Lemma 2.2Suppose that{Gt(·):t≥0}is the stationary Markov random graph process in Theorem2.1.Then∀t≥0,the probability of{Gt(·):t≥0}having no interval isolated nodes on[0,t]is

where

ProofSuppose that the random adjacency matrix process according to{Gt(·):t≥0}is

Suppose further thatAiis a random event,iis an isolated node on[0,t],i=1,2,···,N.Then

Generally,for anykdifferent events,similarly,we can get

According to the multi-less complement principle,

So

This completes the proof.

Theorem 2.2Suppose that{Gt(·):t≥0}is the stationary Markov random graph process in Theorem2.1.Then∀t≥0,ξ(ω;0,t)is the number of interval isolated nodes of{Gt(·):t≥0}on[0,t],and its distribution is

where

ProofAccording to Lemma 2.2,

Suppose thatAiis a random event,iis an interval isolated node onAccording to the total probability formula and Lemma 2.2,for

where

This completes the proof.

Remark 2.2Because{Gt(·):t≥0}is the stationary Markov random graph process,according to its stationarity,∀t0≥0,t≥0,ξ(ω;t0,t0+t)is the number of interval isolated nodes on[t0,t0+t],and it has the same distribution asξ(ω;0,t),that is to say,the distribution ofξ(ω;t0,t0+t)has nothing to do witht0,but only has something to do with the interval lengtht.

Theorem 2.3Suppose that{Gt(·):t≥0}is the stationary Markov random graph process in Theorem2.1.Then whenhas no isolated node at any time t≥0and no interval isolated node on any interval.

ProofForV=V(Gt(·)),t≥0,∀i∈V,Aiare random events,iis the isolated node.∀i/=j,Aijdenotes thatiandjare disconnected.Then

Therefore,

Then

Namely,{Gt(·):t≥0}has no isolated node at any timet≥0.Similarly,we can also prove that it has no interval isolated node on any interval.

This completes the proof.

Corollary 2.1Suppose0＜q＜1.Then

The proof of Corollary 2.1 can be obtained directly from Theorems 2.1 and 2.3.However,it is worth noting that to prove the corollary by the method usually used to derive limit does not seem obvious.By applying the random graph method,Corollary 2.1 gives an interesting limit of the sum formula.

3 Connection Probability

Suppose thatGis a graph.A pathway ofGrefers to a finite non-empty sequenceW=V0e1V1e2···ekVk.Wis a pathway fromV0toVk,and integerkis called the length of the pathwayW.A pathway with lengthkis de fined ask-pathway.

In the sample graph,pathwayV0e1V1e2···ekVkis determined by its vertices sequenceV0V1···Vk,so the pathway of the sample graph is also denoted by its vertices sequence.Even in a non-simple graph,in the case of no ambiguity,we also use the vertices sequence to represent a pathway.

Suppose thatG(ω)is an undirected random graph.Forω0∈Ω andu,v∈V(G(ω0)),if there is a pathway fromutoVinG(ω),thenuandvare de fined as connected inG(ω).Suppose Ω0⊆Ω.If∀ω∈ω0,uandvare connected inG(ω),then we calluandvare connected inG(ω)on Ω0.Specially,ifP(Ω0)=1,thenuandvare de fined as almost everywhere connected on Ω.If any two nodes inG(ω)are almost everywhere connected,thenG(ω)is de fined as an almost everywhere connected random graph,andGis abbreviatedly called a connected random graph.

Lemma 3.1(see[3])Suppose that{Gt(·):t≥0}is an independent identically distribution edge-Markovian random graph process which has stationary distribution as its initial distribution in Theorem2.1,where V(Gt(ω))={1,2,···,N},t≥0.Then∀t≥0,the probability of Gt(·)existing a k-pathway(k≥1)in which i is the start point is

ProofAssumei=1,and suppose thatA1jis a random event,nodes 1 andjare connected,2≤j≤N.Suppose thatAj(k)denotes a random event:There is ak-pathway in whichjis the start point,1≤j≤N,k≥1.Next,we prove the lemma by the mathematical induction method.

Whenk=1,the conclusion is obviously established.In fact,

Suppose that the conclusion is established whenk−1,namely,

So the conclusion is established according to the principle of induction.

This completes the proof.

Lemma 3.2(see[3])Suppose that{Gt(·):t≥0}is an independent identically distribution edge-Markovian random graph process which has stationary distribution as its initial distribution in Theorem2.1,where V(Gt(ω))={1,2,···,N},t≥0.For i,j∈V(Gt(ω)),suppose that Aij(k)denotes a random event:There is a k-pathway in which i is the start point,and j is the end point.Then

This completes the proof.

Theorem 3.1Suppose that{Gt(·):t≥0}is an independent identically distribution edge-Markovian random graph process which has stationary distribution as its initial distribution in Theorem2.1,where V(Gt(ω))={1,2,···,N},t≥0.∀i,j∈V(Gt(ω)),Cijdenotes the event:Nodes i and j are connected.Then

ProofSuppose thatςijdenotes the length of the pathway(+∞can be obtained)in whichiis the start point,andjis the end point.Thenςijis a random variable which can obtain the positive integer value or+∞.From Lemma 3.2,we have

This completes the proof.

Theorem 3.2Suppose that{Gt(·):t≥0}is a random graph process in Theorem2.1,and C denotes the random event:Gt(ω)is connected.Then

(2)Whenis almost everywhere connected.

Proof

Obviously,

This completes the proof.

[1]Barabasi,A.L.,Linked:The New Science of Networks,Persus Publishing,Massachusotts,1979.

[2]Watts,D.J.,The “new” science of networks,Annual Review of Sociology,30,2004,243–270.

[3]Jodan,J.,The degree sequences and spectra of scale-free random graph,Random Structures and Algorithms,29,2006,226–242.

[4]An,L.and Liu,X.R.,The stability analysis of random growing networks,Journal of Hebei University of Technology,39,2010,17–19.

[5]Cao,Y.,The degree distribution of randomk-trees,Theoretical Computer Science,410,2009,688–695.

[6]Han,D.,The stationary distribution of a continuous-time random graph process with interacting edges,Acta Math.Phy.Sinica,14,1994,98–102.

[7]Avin,C.,Koucky,M.and Lotker,Z.,How to explore a fast-changing world,Proc.of the 35th International Colloquium on Automata,Languages and Programming,Springer-Verlag,Berlin,2008,121–132.

[8]Clementi,A.E.F.,Macci,C.,Monnti,M.,et al.,Flooding time in edge-markovian dynamic graphs,Proc.of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing(PODC),ACM Press,New York,2008,213–222.

[9]Herv,B.,Pierluigi,C.and Pierre,F.,Parsimonious flooding in dynamic graphs,Proc.of the 28th ACM Symposium on Principles of Distributed Computing,Calgary,ACM Press,USA,2009,260–269.

[10]Cai,Q.S.and Niu,J.W.,Opportunity network time evolution graph model based on the edge independent evolution,Computer Engineering,37(15),2011,17–22.

[11]Du,C.F.,Markov chain model of the random network,Science Technology and Engineering,10(30),2010,7380–7383.