Community Detection in Networks using Graph Distance

Introduction

The study of networks has received increased attention recently not only from the social sciences and statistics but also from physicists, computer scientists and mathematicians. With the information boom, a huge number of network data sets have come into prominence. In biology - gene transcription networks, protein-protein interaction network, in social media - Facebook, Twitter, Linkedin networks, information networks arising in connection with text mining, technological networks such as the Internet, ecological and epidemiological networks and many others have appeared. Although the study of networks has a long history in physics, social sciences and mathematics literature and informal methods of analysis have arisen in many fields of application, statistical inference on network models as opposed to descriptive statistics, empirical modeling and some Bayesian approaches has not been addressed extensively in the literature. A mathematical and systematic study of statistical inference on network models has only started in recent years.

One of the fundamental questions in analysis of such data is detecting and modeling community structure within the network. A lot of algorithmic approaches to community detection have been proposed, particularly in the physics and computer science literature . In terms of community detection, there are two different goals that researchers have tried to pursue -

Algorithmic Goal: Identify the community each vertex of the network belongs to.

Theoretical Goal: If the network is generated by an underlying generative model, then, what is the probability of success for the algorithm.

Several popular algorithms for community detection have been proposed in physics, computer science and statistics literature. Most of these algorithms show decent performance in community detection for selected real-world and simulated networks and have polynomial time complexity. We shall briefly mention some of these algorithms.

Modularity maximizing methods . One of the most popular method of community detection. The problem is NP hard but spectral relaxations of polynomial complexity exist .

Spectral clustering based methods , . These methods are also very popular. Most of the time these methods have linear or polynomial running times. Mostly shown to work for dense graphs only.

Profile likelihood maximization . The problem is NP hard, but heuristic algorithms have been proposed, which have good performance for dense graphs.

MCMC based likelihood maximization by Gibbs Sampling, the cavity method and belief propagation based on stochastic block model.

Variational Likelihood Maximization based on stochastic block model , . Polynomial running time but appears to work only for dense graphs.

Pseudo-likelihood Maximization . Fast method which works well for both dense and sparse graphs. But the method is not fully justified.

Mixed Membership Block Model . Iterative method and works for dense graphs. The algorithm for this model is based on variational approximation of the maximum likelihood estimation.

Degree-corrected block model : Incorporates degree inhomogeneity in the model. Algorithms based on maximum likelihood and profile likelihood estimation has been developed.

Overlapping stochastic block model : Stochastic block model where each vertex can lie within more than one community. The algorithm for this model is based on variational approximation of the maximum likelihood estimation.

Mixed configurations model : Another extension to degree-corrected stochastic block model, where, the model is a mixture of configurations model (degree-corrected block model with one block) and each vertex can lie in more than one community. The algorithm for this model is based on the EM algorithm and maximum likelihood estimation.

2 Theoretical Goal

The stochastic block model (SBM) is perhaps the most commonly used and best studied model for community detection. An SBM with $Q$ blocks states that each node belongs to a community $\boldsymbol{c}=(c_{1},\ldots,c_{n})\in\{1,\ldots,Q\}$ which are drawn independently from the multinomial distribution with parameter $\boldsymbol{\pi}=(\pi_{1},\ldots,\pi_{Q})$, where $\pi_{i}>0$ for all $i$, and $Q$ is the number of communities, assumed known. Conditional on the labels, the edge variables $A_{ij}$ for $i<j$ are independent Bernoulli variables with

where $P=[P_{ab}]$ and $K=[K_{ab}]$ are $Q\times Q$ symmetric matrix. $P$ can be considered the connection probability matrix, where as $K$ is the kernel matrix for the connection. So, we have $P_{ab}\leq 1$ for all $a,b=1,\ldots,Q$, $P\mathbf{1}\leq\mathbf{1}$ and $\mathbf{1}^{T}P\leq\mathbf{1}$ element-wise. The network is undirected, so $A_{ji}=A_{ij}$, and $A_{ii}=0$ (no self-loops). The problem of community detection is then to infer the node labels $\boldsymbol{c}$ from $A$. Thus we are not really interested in estimation or inference on parameters $\boldsymbol{\pi}$ and $P$, but, rather we are interested in estimating $\boldsymbol{c}$. But, it does not mean the two problems are mutually exclusive. In reality, the inferential problem and the community detection problem are quite interlinked.

The theoretical results of community detection for stochastic block models can be divided into 3 different regimes -

All of the above mentioned algorithms perform satisfactorily on regime (a).

None of the above algorithms have been shown to have near perfect probability of success under either regime (b) or (c), for the full parameter space. Some algorithms like are shown to partially work in the sparse setting. Some very recent algorithms include .

In this paper, we shall only concentrate on stochastic block models. In the future, we shall try to extend our method and results for more general models.

3 Contributions and Outline of the Chapter

Our algorithm is based on graph distance between vertices of the graph. We perform spectral clustering based on the graph distance matrix of the graph. By looking at the graph distance matrix instead of adjacency matrix for spectral clustering increases the performance of the community detection, as the normalized distance between cluster centers increases when we go from the adjacency matrix to the graph distance matrix. This helps in community detection even for sparse matrices. We only show theoretical results for stochastic block models. The theoretical proofs are quite intricate and involve careful coupling of the stochastic block model with multi-type branching process to find asymptotic distribution of the typical graph distances. Then, a careful analysis of the eigenvector of the asymptotic graph distance matrix reveals the existence of separation needed for spectral clustering to succeed. This method of analysis has been used for spectral clustering analysis using the adjacency matrix also , but the analysis is simpler.

The rest of the paper is organized as follows. We give a summary of the preliminary results needed in Section 2. We present the algorithms in Section 3. We give an outline of proof of theoretical guarantee of performance of the method and then the details in Section 4. The numerical performance of the methods is demonstrated on a range of simulated networks and on some real world networks in Section 5. Section 6 concludes with discussion, and the Appendix contains some additional technical results.

Preliminaries

Let us suppose that we have a random graph $G_{n}$ as the data. Let $V(G_{n})=\{v_{i},\ldots,v_{n}\}$ denote the vertices of $G_{n}$ and $E(G_{n})=\{e_{1},\ldots,e_{m}\}$ denote the edges of $G_{n}$. So, the number of vertices in $G_{n}$ is $|V(G_{n})|=n$ and number of edges of $G_{n}$ is $|E(G_{n})|=m$. Let the adjacency matrix of $G_{n}$ be denoted by $A_{n\times n}$. For the sake of notational simplicity, from here onwards we shall denote $G_{n}$ by $G$ having $n$ vertices unless specifically mentioned. We consider the $n$ vertices of $G$ are clustered into $Q$ different communities with each community having size $n_{a}$, $a=1,\dots,Q$ and $\sum_{a}n_{a}=n$. In this paper, we are interested in the problem of vertex community identification or graph partitioning. That means that we are interested in finding which of the $Q$ different community each vertex of $G$ belongs to. However, the problem is an unsupervised learning problem. So, we assume that the data is coming from an underlying model and we try to verify how good ‘our’ community detection method works for that model.

As a model for community detection, we consider the stochastic block model. We shall define the stochastic block model shortly, but, we first we shall introduce some more general models, of which stochastic block model is a special case.

The general non-parametric model, as described in Bickel, Chen and Levina (2011) , that generates the random data network $G$ can be defined by the following equation -

where, $w(u,v)\geq 0$, symmetric, $0\leq u,v\leq 1$, $\rho_{n}\rightarrow 0$. For block models, the latent variable for each vertex $(\xi_{1},\ldots,\xi_{n})$ can be considered to be coming from a discrete and finite set. Then, each element of that set can be considered to be inducing a partition in the vertex set $V(G_{n})$. Thus, we get a model for vertex partitioning, where, the set of vertices can be partitioned into finite number of disjoint classes, but however the partition to which each vertex belongs to is the latent variable in the model and thus unknown. The main goal becomes estimating this latent variable.

1.2 Inhomogeneous Random Graph Model

The inhomogeneous random graph model (IRGM) was introduced in Bollobás et. al. (2007) . Let $\mathcal{S}$ be a separable metric space equipped with a Borel probability measure $\mu$. For most cases $\mathcal{S}=(0,1]$ with $\mu$ Lebesgue measure, that means a $U(0,1)$ distribution. The “kernel” $\kappa$ will be a symmetric non-negative function on $\mathcal{S}\times\mathcal{S}$. For each $n$ we have a deterministic or random sequence $\boldsymbol{x}=(x_{1},\ldots,x_{n})$ of points in $\mathcal{S}$. Writing $\delta_{x}$ for the measure consisting of a point mass of weight 1 at $x$, and

for the empirical distribution of $\boldsymbol{x}$, it is assumed that $\nu_{n}$ converges in probability to $\mu$ as $n\rightarrow\infty$, with convergence in the usual space of probability measures on $\mathcal{S}$. One example where the convergence holds is the random case, where the $x_{i}$ are independent and identically distributed on $\mathcal{S}$ with distribution $\mu$ convergence in probability holds by the law of large numbers. Of course, we do not need $(x_{n})_{n\geq 1}$ to be defined for every $n$, but only for an infinite set of integers $n$. From here onwards, we shall only focus on this special case, where, $(x_{1},\ldots,x_{n})\stackrel{{\scriptstyle iid}}{{\sim}}\mu$.

A kernel $\kappa_{n}$ on a ground space $(\mathcal{S},\mu)$ is a symmetric non-negative (Borel) measurable function on $\mathcal{S}\times\mathcal{S}$. $\kappa$ is also continuous a.e. on $\mathcal{S}\times\mathcal{S}$. By a kernel on a vertex space $(\mathcal{S},\mu,(x_{n})_{n\geq 1})$ we mean a kernel on $(\mathcal{S},\mu)$.

Given the (random) sequence $(x_{1},\ldots,x_{n})$, we let $G(n,\kappa)$ be the random graph $G(n,(p_{ij}))$ with

In other words, $G^{\mathcal{V}}(n,\kappa)$ has $n$ vertices $\{1,\ldots,n\}$ and, given $x_{1},\ldots,x_{n}$, an edge $ij$ (with $i\neq j$) exists with probability $p_{ij}$, independently of all other (unordered) pairs $ij$. Based on the graph kernel we can also define an integral operator $T_{\kappa}$ in the following way

The integral operator $T_{\kappa}:L^{2}(\mathcal{S})\rightarrow L^{2}(\mathcal{S})$ corresponding to $G(n,\kappa)$, is defined as

where, $x\in\mathcal{S}$ and any measurable function $f\in L^{1}(\mathcal{S})$.

The random graph $G(n,\kappa)$ depends not only on $\kappa$ but also on the choice of $x_{1},\ldots,x_{n}$. The freedom of choice of $x_{i}$ in this model gives some more flexibility than Bickel-Chen model. The asymptotic behavior of $G(n,\kappa)$ depend very much on $\mathcal{S}$ and $\mu$. Many of these key results such as existence of giant component, typical distance, phase transition properties are proved in . We shall use these results on inhomogeneous random graphs in order to prove results on graph distance for stochastic block models.

Here is further comparison of the Inhomogeneous random graph model (IRGM) with the Bickel-Chen model (BCM), to understand their similarities and dissimilarities -

In BCM, $(\xi_{1},\ldots,\xi_{n})\stackrel{{\scriptstyle iid}}{{\sim}}U(0,1)$ are the latent variables associated with the vertices $(v_{1},\ldots,v_{n})$ of random graph $G_{n}$. Similarly, in IRGM, $(x_{1},\ldots,x_{n})\sim\mu$ are the latent variables associated with the vertices $(v_{1},\ldots,v_{n})$ of random graph $G_{n}$. Now, if in IRGM, $(x_{1},\ldots,x_{n})\stackrel{{\scriptstyle iid}}{{\sim}}\mu$ then the latent variable structure of the two models become equivalent.

In BCM, the conditional probability of connection between two vertices given the value of their latent variables is controlled by the kernel function $h_{n}(u,v)$. In IRGM, the conditional probability of connection between two vertices given the value of their latent variables is controlled by the kernel function $\frac{\kappa(u,v)}{n}$.

where, $T_{\kappa}$ is the operator define in Definition 2.2 and $||\cdot||$ is the operator norm. In BCM,

If BCM and IRGM have same underlying measure spaces $(\mathcal{S}=(0,1),\mu=U(0,1))$ and $h_{n}(u,v)=\kappa(u,v)/n$ and

$\mathbf{1}$ is the principal eigenfunction of $T_{\kappa}$, then

$\mathbf{1}$ is not the principal eigenfunction of $T_{\kappa}$, then

1.3 Stochastic Block Model

The stochastic block model is perhaps the most commonly used and best studied model for community detection. We continue with IRGM framework, so the graph is sparse.

A graph $G^{Q}(,(P,\boldsymbol{\pi}))$ generated from stochastic block model (SBM) with $Q$ blocks and parameters $P\in(0,1)^{Q\times Q}$ and $\boldsymbol{\pi}\in(0,1)^{Q}$ can be defined in following way - each vertex of graph $G_{n}$ from an SBM belongs to a community $\boldsymbol{c}=(c_{1},\ldots,c_{n})\in\{1,\ldots,Q\}$ which are drawn independently from the multinomial distribution with parameter $\boldsymbol{\pi}=(\pi_{1},\ldots,\pi_{Q})$, where $\pi_{i}>0$ for all $i$. Conditional on the labels, the edge variables $A_{ij}$ for $i<j$ are independent Bernoulli variables with

where $P=[P_{ab}]$ and $K=[K_{ab}]$ are $Q\times Q$ symmetric matrices. $P$ is known as the connection probability matrix and $K$ as the kernel matrix for the connection. So, we have $P_{ab}\leq 1$ for all $a,b=1,\ldots,Q$, $P\mathbf{1}\leq\mathbf{1}$ and $\mathbf{1}^{T}P\leq\mathbf{1}$ element-wise.

The network is undirected, so $A_{ji}=A_{ij}$, and $A_{ii}=0$ (no self-loops). The problem of community detection is then to infer the node labels $\boldsymbol{c}$ from $A$. Thus we are not really interested in estimation or inference on parameters $\boldsymbol{\pi}$ and $P$, but, rather we are interested in estimating $\boldsymbol{c}$. But, it does not mean the two problems are mutually exclusive, in reality, the inferential problem and the community detection problem are quite interlinked.

We can see that SBM is a special case of both Bickel-Chen model and IRGM. In IRGM, if we consider $\mathcal{S}$ to be a finite set, $(x_{1},\ldots,x_{n})\in[Q]^{n}$ ($[Q]=\{1,\ldots,Q\}$) with $x_{i}\stackrel{{\scriptstyle iid}}{{\sim}}Mult(n,\boldsymbol{\pi})$ and kernel $\kappa:[Q]\rightarrow[Q]$ as $\kappa(a,b)=K_{ab}$ ($a,b=1,\ldots,Q$), then the resulting IRGM graph follows stochastic block model. So, for SBM we can define an integral operator on $[Q]$ with measure $\{\pi_{1},\ldots,\pi_{Q}\}$.

The stochastic block model has deep connections with Multi-type branching process, just as, Erodös-Rényi random graph model (ERRGM) has connections with the branching process. Let us introduce branching process first.

2 Multi-type Branching Process

We shall try to link network formed by SBM with the tree network generated by multi-type Galton-Watson branching process. In our case, the Multi-type branching process (MTBP) has type space $S=\{1,\ldots,Q\}$, where a particle of type $a\in S$ is replaced in the next generation by a set of particles distributed as a Poisson process on $S$ with intensity $(K_{ab}\pi_{b})_{b=1}^{Q}$. We denote this branching process, started with a single particle of type $a$, by $\mathcal{B}_{K,\pi}(a)$. We write $\mathcal{B}_{K,\pi}$ for the same process with the type of the initial particle random, distributed according to $\boldsymbol{\pi}$.

Define $\rho_{k}(K,\pi;a)$ as the probability that the branching process $\mathcal{B}_{K,\pi}(a)$ has a total population of exactly $k$ particles.

Define $\rho_{\geq k}(K,\pi;a)$ as the probability that the total population is at least $k$.

Define $\rho(K,\pi;a)$ as the probability that the branching process survives for eternity.

and define $\rho_{\geq k}(K)$ analogously. Thus, $\rho(K,\pi)$ is the survival probability of the branching process $\mathcal{B}_{K,\pi}$ given that its initial distribution is $\boldsymbol{\pi}$

If the probability that a particle has infinitely many children is 0, then $\rho(K,\pi;a)$ is equal to $\rho_{\infty}(a)$, the probability that the total population is infinite. As we shall see later, the branching process $\mathcal{B}_{K,\pi}(a)$ arises naturally when exploring a component of $G_{n}$ starting at a vertex of type $a$; this is directly analogous to the use of the single-type Poisson branching process in the analysis of the Erdös-Rényi graph $G(n,c/n)$.

3 Known Results for Stochastic Block Model

The performance of community detection algorithms depends on the parameters $\boldsymbol{\pi}$ and $P$. We refer to Definition 2.3 for definition of stochastic block models. An important condition that we usually put on parameter $P$ is irreducibility.

A connection matrix $P$ on a $\mathcal{S}=\{1,\ldots,Q\}$ is reducible if there exists $A\subset\mathcal{S}$ with $0<|A|<Q$ such that $P=0$ a.e. on $A\times(\mathcal{S}-A)$; otherwise $P$ is irreducible. Thus $P$ is irreducible if $A\subseteq\mathcal{S}$ and $P=0$ a.e. on $A\times(\mathcal{S}-A)$ implies $|A|=0$ or $|A|=Q$.

So, the results on existence of giant components in also apply for SBM. The following theorem describes the result on existence of giant components.

Let us define operator $T_{K}$ as in definition 2.4,

If $||T_{K}||\leq 1$ ($||\cdot||$ refer to operator norm), then the size of largest component is $o_{P}(n)$, while if $||T_{K}||>1$, then the size of largest component is $\Theta_{P}(n)$ whp.

If $P$ is irreducible, then $\frac{1}{n}(\mbox{Size of largest component})\rightarrow\boldsymbol{\pi}^{T}\rho$, where, $\rho\in^{Q}$ is the survival probability as defined in (5).

The theoretical results on community detection depend on the 3 different regime on which the generative model is based on -

If $(a-b)^{2}<2(a+b)$ then probability model of SBM and ERRGM with $p=\frac{a+b}{2n}$ are mutually contiguous. Moreover, if $(a-b)^{2}<2(a+b)$, there exists no consistent estimators of $a$ and $b$.

If $(a-b)^{2}>2(a+b)$ then probability model of SBM and ERRGM with $p=\frac{a+b}{2n}$ are asymptotically orthogonal.

So, in the range $(a-b)^{2}>2(a+b)$, there should exists an algorithm which identifies highly correct clustering with high probability at least within the giant components.

Algorithm

The algorithm we propose depend on the graph distance or geodesic distance between vertices in a graph.

Graph distance or Geodesic distance between two vertices $i$ and $j$ of graph $G$ is given by the length of the shortest path between the vertices $i$ and $j$, if they are connected. Otherwise, the distance is infinite.

So, for any two vertices $u,v\in V(G)$, graph distance, $d_{g}$ is defined by

For sake of numerical convenience, we shall replace $\infty$ by a large number for value of $d_{g}(u,v)$, when, $u$ and $v$ are not connected. The main steps of the algorithm can be described as follows

Find the graph distance matrix $D=[d_{g}(v_{i},v_{j})]_{i,j=1}^{n}$ for a given network but with distance upper bounded by $k\log n$. Assign non-connected vertices an arbitrary high value $B$.

Perform hierarchical clustering to identify the giant component $G^{C}$ of graph $G$. Let $n_{C}=|V(G^{C})|$.

Normalize the graph distance matrix on $G^{C}$, $D^{C}$ by

Perform eigenvalue decomposition on $\bar{D}^{C}$.

Here are some important observations about the algorithm -

There are standard algorithms for graph distance finding in the algorithmic graph theory literature. In algorithmic graph theory literature the problem is known as the all pairs shortest path problem. The two most popular algorithms are Floyd-Warshall and Johnson’s algorithm . The time complexity of the Floyd-Warshall algorithm is $O(n^{3})$, where as, the time complexity of Johnson’s algorithm is $O(n^{2}\log n+ne)$ ($n=|V(G_{n})|$ and $e=|E(G_{n})|$). So, for sparse graphs, Johnson’s algorithm is faster than Floyd-Warshall. Memory storage is also another issue for this algorithm, since the algorithm involves a matrix multiplication step of complexity $\Omega(n^{2})$. Recently, there also has been some progress on parallel implementation of all-pairs shortest path problem , which addresses both memory and computation aspects of the algorithm and lets us scale the algorithm for large graphs, both dense and sparse.

is minimized. The minimizer is attained by the rows of the matrix formed by the top $Q$ eigenvectors of $\bar{D}^{C}$ as columns. So, performing spectral clustering on $\bar{D}^{C}$ is the same as performing $Q$-means clustering on the multi-dimensional scaled space.

Instead of $\bar{D}^{C}$, we could also use the matrix $(D^{C})^{2}$, but then, the topmost eigenvector does not carry any information about the clustering. Similarly, we can also use the matrix $D^{C}$ directly for spectral clustering, but, in that case, $D^{C}$ is not a positive semi-definite matrix and as a result we have to consider the eigenvectors corresponding to largest absolute eigenvalues (since eigenvalues can be negative).

In the Step 5 of the algorithm $Q$-means clustering if the expected degree of the blocks are equal. However, if the expected degree of the blocks are different, it leads to multi scale behavior in the eigenvectors of the normalized distance matrix. So, we perform Gaussian Mixture Model (GMM) based clustering instead of $Q$-means to take into account the multi scale behavior.

Theory

Let us consider that we have a random graph $G_{n}$ as the data. Let $V(G_{n})=\{v_{i},\ldots,v_{n}\}$ denote the vertices of $G_{n}$ and $E(G_{n})=\{e_{1},\ldots,e_{m}\}$ denote the edges of $G_{n}$. So, the number of vertices in $G_{n}$ is $|V(G_{n})|=n$ and number of edges of $G_{n}$ is $|E(G_{n})|=m$. Let the adjacency matrix of $G_{n}$ be denoted by $A_{n\times n}$. For sake of notational simplicity, from here onwards we shall denote $G_{n}$ by $G$ having $n$ vertices unless specifically mentioned. There are $Q$ communities for the vertices and each community has $(n_{a})_{a=1}^{Q}$ number of vertices. In this paper, we are interested in the problem of vertex community identification or graph partitioning. However, the problem is an unsupervised learning problem. So, we assume that the data is coming from an underlying model and we try to verify how good ‘our’ community detection method works for that model.

The theoretical analysis of the algorithm has two main parts -

Finding the limiting distribution of graph distance between two typical vertices of type $a$ and type $b$ (where, $a,b=1,\ldots,Q$). This part of the analysis is highly dependent on results from multi-type branching processes and their relation with stochastic block models. The proof techniques and results are borrowed from , and .

Finding the behavior of top $Q$ eigenvectors of the graph distance matrix $D$ using the limiting distribution of the typical graph distances. This part of analysis is highly dependent on perturbation theory of linear operators. The proof techniques and results are borrowed from , and .

Let $\lambda>1$ (defined in Eq. (8)), then, the graph distance $d_{G}(u,v)$ between two uniformly chosen vertices of type $a$ and $b$ respectively, conditioned on being connected, satisfies the following asymptotic relation -

In Theorem 4.1 we had a point-wise result, so, we combine these point-wise results to give a matrix result -

Let $\lambda=||T_{K}||>1$, then, within the big connected component,

Thus, the above theorem gives us an idea about the limiting behavior of the normalized version of geodesic matrix $\mathbf{D}$.

A rough idea of the proof of part I is as follows. Fix two vertices, say 1 and 2, in the giant component. Think of a branching process starting from vertices of type 1 and 2, so that at time $t$, $\mathcal{B}_{P\pi}(a)(t)$ is the branching process tree from vertex of type $a$ and includes the shortest paths to all vertices in the tree at or before time $t$ from vertex $a$, $a=1,2$. When these two trees meet via the formation of an edge $(v_{1},v_{2})$ between two vertices $v_{1}\in\mathcal{B}_{P\pi}(1)(\cdot)$ and $v_{2}\in\mathcal{B}_{P\pi}(2)(\cdot)$, then the shortest-length path between the two vertices 1 and 2 has been found. If $D_{n}(v_{a})$, $a=1,2$, denotes the number of edges between the source $a$ and the vertex $v_{a}$ along the tree $\mathcal{B}_{P\pi}(a)$, then the graph distance $d_{n}(1,2)$ is given by

The above idea is indeed a very rough sketch of our proof and it follows from the graph distance finding idea developed in . In the paper, we embed the SBM in a multi-type branching process (MTMBP) or a single-type marked branching process (MBP), depending on whether the types of two vertices are same or not. The offspring distribution is binomial with parameters $n-1$ and kernel $P$ (see Section 4.4). With high probability, the vertex exploration process in the SBM can be coupled with two multi-type branching processes, bounding the vertex exploration process on SBM on both sides. Now, using the property of the two multi-type branching processes, we can bound the number of vertices explored in the vertex exploration process of a SBM graph and infer about the asymptotic limit of the graph distance.

With the above sketch of proof can be organized as follows.

We analyze various properties of a Galton-watson process conditioned on non-extinction, including times to grow to a particular size. In this branching process, the offspring will have a Poisson distribution.

We introduce multi-type branching process trees with binomially distributed offspring and make the connection between these trees and the SBM. We bound the vertices explored for an SBM graph, starting from a fixed vertex, by considering a muti-type branching process coupled with it.

We bound the geodesic distance using the number of vertices explored in the coupled multi-type branching processes within a certain generation. The limiting behavior of the generation give us the limiting behavior of graph distance.

The whole analysis is true for IRGM. So, the results are true for SBM with increasing block numbers and degree-corrected block models also.

The idea of the argument is quite simple, but making these ideas rigorous takes some technical work, particularly because we need to condition on our vertices being in the giant component.

2 Results of Part II

The limiting kernel matrix, $\mathcal{D}_{Q\times Q}$ is defined as

Now, we assume some conditions on the limiting low-dimensional matrix $\mathcal{D}$.

The eigenvalues of $\mathcal{D}$, $\lambda_{1}(\mathcal{D})\geq\cdots\geq\lambda_{Q}(\mathcal{D})$, satisfy the condition that there exists an constant $\alpha$, such that, $0<\alpha\leq\lambda_{Q}(\mathcal{D})$.

The number of vertices in each type $(n_{1},\ldots,n_{Q})$, satisfy the condition that there exists a constant $\theta$ such that $0<\theta<\frac{n_{a}}{n}$ for all $a=1,\ldots,Q$ and all $n$.

3 Branching Process Results

Let us recall our notation for the survival probabilities of particles in $\mathcal{B}_{K}(a)$. We write $\rho_{k}(K;a)$ for the probability that the total population consists of exactly $k$ particles, and $\rho_{\geq k}(K;a)$ for the probability that the total population contains at least $k$ particles. Furthermore, $\rho(K;a)$ is the probability that the branching process survives for eternity. We write $\rho_{k}(K),\rho_{\geq k}(K)$ and $\rho(K)$ for the corresponding probabilities for $\mathcal{B}_{K}$ , so that, e.g., $\rho_{k}(K)=\sum_{a=1}^{Q}\rho_{k}(K;a)\pi_{a}$.

Now, we try to find a coupling relation between neighborhood exploration process of a vertex of type $a$ in stochastic block model and multi-type Galton-Watson process, $\mathcal{B}(a)$ starting from a vertex of type $a$.

We assume all vertices of graph $G_{n}$ generated from a stochastic block model has been assigned a community or type $\xi_{i}$ (say) for vertex $v_{i}\in V(G_{n})$. By neighborhood exploration process of a vertex of type $a$ in stochastic block model, we mean that we start from a random vertex $v_{i}$ of type $a$ in the random graph $G_{n}$ generated from stochastic block model. Then, we count the number of vertices of the random graph $G_{n}$ are neighbors of $v_{i}$, $N(v_{i})$. We repeat the neighborhood exploration process by looking at the neighbors of the vertices in $N(v_{i})$. We continue until we have covered all the vertices in $G_{n}$. Since, we either consider $G_{n}$ connected or only the giant component of $G_{n}$, the neighborhood exploration process will end in finite steps but the number of steps may depend on $n$.

Within the giant component, the neighborhood exploration process for a stochastic block model graph with parameters $(P,\pi)=(K/n,\pi)$, can be bounded with high probability by two multi-type branching processes with kernels $(1-2\epsilon)K$ and $(1+\epsilon)K$ for some $\epsilon>0$.

The proof is given in Appendix A1 and follows from Lemma 9.6 . ∎

Now, we restrict ourselves to the giant component only. So, if we condition that the exploration process does not leave the giant component, it is same as conditioning that the branching process does not die out. Under this additional condition, the branching process can be coupled with another branching process with a different kernel. The kernel of that branching process is given in following lemma.

If we condition a branching process, $\mathcal{B}_{K\pi}$ on survival, the new branching process has kernel $\left(K_{ab}\left(\rho(K;a)+\rho(K;b)-\rho(K;a)\rho(K;b)\right)\right)_{a,b=1}^{Q}$.

The proof is given in Appendix A2 and follows from Section 10 of . ∎

Now, we shall try to prove the limiting behavior of typical distance between vertices $v$ and $w$ of $G_{n}$, where, $v,w\in V(G_{n})$. We first try to find a lower bound for distance between two vertices. We shall separately give an upper bound and lower bound for distance between two vertices of same type and different types. The result on lower bound in proved in Lemma 4.8.

type of $v=a\neq b=$ type of $w$ (say) and $\lambda\equiv||T_{K}||>1$, then,

type of $v=$ type of $w=a$ (say), $\lambda\equiv||T_{K}||<\pi_{a}K_{aa}$ and $\lambda>1$, then,

The proof is given in Appendix A3 and follows from Lemma 14.2 of . ∎

Now, we first try to upper bound the typical distance between two vertices of the same type. For the same type vertices, we just focus on the subgraph of the original graph from stochastic block model having vertices of same type. So, in Lemma 4.9, the graph $G_{n}$ is the subgraph of the original graph containing only the vertices of the same type. So, the coupled branching process on that graph automatically becomes a single-type branching process.

For vertices $v,w\in V(G)$, if type of $v=$ type of $w=a$ (say)

conditioned on the event that the branching process $\mathcal{B}_{K_{aa}}(a)$ survives.

The proof is given in Appendix A4 and follows from Lemma 14.3 of . ∎

Now, let us try to upper bound the typical distance between two vertices of different types. So, in Lemma 4.10, the graph $G_{n}$ is the original graph containing with vertices of the different types. So, the coupled branching process on that graph becomes a multi-type branching process.

conditioned on the event that the branching process $\mathcal{B}_{K}$ survives.

The proof is given in Appendix A5 follows from Lemma 14.3 of . ∎

4 Proof of Theorem 4.1 and Theorem 4.3

We shall try to prove the limiting behavior of typical graph distance in the giant component as $n\rightarrow\infty$. The Theorem essentially follows from Lemma 4.8 - 4.10. Under the conditions mentioned in the Theorem, part (a) follows from Lemma 4.8(b) and 4.9 and part (b) follows from Lemma 4.8(a) and 4.10.

4.2 Proof of Theorem 4.3

From the definition 4.2, we have that $\mathbf{D}_{ij}=$ graph distance between vertices $v_{i}$ and $v_{j}$, where, $v_{i},v_{j}\in V(G_{n})$.

For the case when type of $v_{i}=$ type of $v_{j}=a$ (say) From Lemma 4.8(b), we get for any vertices $v$ and $w$ of same type $a$ with high probability,

Also from Lemma 4.9, we get, for any vertices $v$ and $w$ of same type $a$

So, we have that, for $v_{i},v_{j}$ having same type $a$, with high probability,

Since, $\epsilon=O(n^{-1/2})$ by Eq (19) and $(1-exp(-\Omega(n^{2\eta})))^{n^{2}}\rightarrow 1$ as $n\rightarrow\infty$,

For the case when type of $v_{i}\neq$ type of $v_{j}$ From Lemma 4.8(a), we get for any vertices $v$ and $w$ with high probability,

So, putting the two statements together, we get that with high probability,

since, by Eq. (19) $\epsilon=O(1/\sqrt{n})$ and and $(1-exp(-\Omega(n^{2\eta})))^{n^{2}}\rightarrow 1$ as $n\rightarrow\infty$.

So, putting the two cases together, we get that with high probability,

5 Perturbation Theory of Linear Operators

The Davis-Kahan Theorem states a bound on perturbation of eigenspace instead of eigenvector, as discussed previously. The $\sin\theta$ Theorem of Davis-Kahan

6 Proof of Theorem 4.5

With high probability it holds that $|\lambda_{Q}(\mathbf{D}/\log n)|\geq O(n)$ and $\lambda_{Q+1}(\mathbf{D}/\log n)\leq O(n^{1-\varepsilon})$.

By Weyl’s Inequality, for all $i=1,\ldots,n$,

So, $|\lambda_{Q}(\mathbf{D}/\log n)|\geq O(n)-O(n^{1-\varepsilon})=O(n)$ for large $n$ and $|\lambda_{Q+1}(\mathbf{D}/\log n)|\leq-1+O(n^{1-\varepsilon})=O(n^{1-\varepsilon})$. ∎

Now, the relationship between the rows of $W$ can be specified based on Assumption (C3) as follows -

For any two rows $i,j$ of $\mathbf{W}_{n\times Q}$ matrix, $||u_{i}-u_{j}||_{2}\geq O(1/\sqrt{n})$, if type of $v_{i}\neq$ type of $v_{j}$.

By Lemma 4.15, for large $n$, we can get constant $C$, such that, $Q$ balls, $B_{1},\ldots,B_{Q}$, of radius $r=Cn^{-1/2}$ around $Q$ distinct rows of $\mathbf{W}$ are disjoint.

Now note that with high probability the number of rows $i$ such that $||\mathbf{C}_{i}-(\mathbf{W}\mathbf{R})_{i}||>r$ is at most $O(n^{1/2-\varepsilon})$. If the statement does not hold then,

So, we get a contradiction, since $||\mathbf{C}-\mathbf{W}\mathbf{R}||_{F}\leq O(n^{-\varepsilon})$. Thus, the number of mistakes should be at most of order $O(n^{1/2-\varepsilon})$.

So, for each $v_{i}\in V(G_{n})$, if $\xi_{i}$ is the type of $v_{i}$ and $\hat{\xi}_{i}$ is the type of $v_{i}$ as estimated from applying $Q$-means on top $Q$ eigenspace of geodesic matrix $\mathbf{D}$, we get that with high probability, for some small $0<\varepsilon$,

Application

We investigate the empirical performance of the algorithm in several different setup. At first, we use simulated networks from stochastic block model to find the empirical performance of the algorithm. Then, we apply our method to find communities in several real world networks.

We simulate networks from stochastic block models with $Q=3$ blocks. Let $w$ correspond to a $Q$-block model defined by parameters $\theta=(\boldsymbol{\pi},\rho_{n},S)$, where $\pi_{a}$ is the probability of a node being assigned to block $a$ as before, and

and the probability of node $i$ to be assigned to block $a$ to be $\pi_{a}$ ($a=1,\ldots,K$).

In the following figures, we try to see the behavior of mean and variances of the count statistics, as we vary $\lambda_{n}$ as we vary $\nu$.

1.2 Unequal Density Clusters

In the following figures, we try to see the behavior of mean and variances of the count statistics, as we vary $\lambda_{n}$ as we vary $\nu$.

2 Application to Real Network Data

In this application, we try to find communities for Facebook collegiate networks. The networks were presented in the paper by Traud et.al. (2011) . The network is formed by Facebook users acting as nodes and if two Facebook users are “friends” there is an edge between the corresponding nodes. Along with the network structure, we also have the data on covariates of the nodes. Each node has covariates: gender, class year, and data fields that represent (using anonymous numerical identifiers) high school, major, and dormitory residence. We consider the network of a specific college (Caltech). We compare the communities found with the dormitory affiliation of the nodes.

2.2 Political Web Blogs Network

This dataset on political blogs was compiled by soon after the 2004 U.S. presidential election. The nodes are blogs focused on US politics and the edges are hyperlinks between these blogs. Each blog was manually labeled as liberal or conservative by , and we treat these as true community labels. We ignore directions of the hyperlinks and analyze the largest connected component of this network, which has 1222 nodes and the average degree of 27. The distribution of degrees is highly skewed to the right (the median degree is 13, and the maximum is 351). This is a network where the degree distribution is heavy-tailed and the graph is inhomogeneous.

Conclusion

We demonstrate the empirical performance of the method by using both simulated and real world networks. We compare with the pseudo-likelihood method and show that they have similar empirical performances. We demonstrate the empirical performance by applying the method for community detection in several real world networks too.

The method also works when number of blocks in the stochastic block model brows with $n$ (number of vertices) and for degree-corrected block model . We conjecture that under these models too the method will have the theoretical guarantee of correct community detection. The proof can be obtained by using similar techniques that we have used in this paper.

References

Appendix: Branching Process Results

We have $n_{a}$ vertices of type $a$ ,$a=1,\ldots,Q$, and that $n_{a}/n\stackrel{{\scriptstyle a.s.}}{{\rightarrow}}\pi_{a}$. From now on we condition on $n_{1},\ldots,n_{Q}$; we may thus assume that $n_{1},\ldots,n_{Q}$ are deterministic with $n_{a}/n\rightarrow\pi_{a}$. Let $\omega(n)$ be any function such that $\omega(n)\rightarrow\infty$ and $\omega(n)/n\rightarrow 0$. We call a component of $G_{n}\equiv G(n,P)=G(n,K/n)$ big if it has at least $\omega(n)$ vertices. Let $B$ be the union of the big components, so $|B|=N_{\geq\omega(n)}(G_{n})$. Fix $\epsilon>0$.We may assume that $n$ is so large that $\omega(n)/n<\epsilon$ $\pi_{i}$ and $|n_{a}/n-\pi_{a}|<\epsilon$ $\pi_{a}$ for every $a$; thus $(1-\epsilon)\pi_{a}n<n_{a}<(1+\epsilon)\pi_{a}n$. We may also assume that $n>\max K$, as $K$ is a function on the finite set $\mathcal{S}\times\mathcal{S}$. Since, $n_{a}/n$ is a $\sqrt{n}$-consistent estimator of $\pi_{a}$, we get that

Select a vertex and explore its component in the usual way, that means looking at its neighbors, one vertex at a time. We first reveal all edges from the initial vertex, and put all neighbors that we find in a list of unexplored vertices; we then choose one of these and reveal its entire neighborhood, and so on. Stop when we have found at least $\omega(n)$ vertices (so $x\in B$), or when there are no unexplored vertices left (so we have found the entire component and $x\notin B$).

Consider one step in this exploration, and assume that we are about to reveal the neighborhood of a vertex $x$ of type $a$. Let us write $n^{\prime}_{b}$ for the number of unused vertices of type $b$ remaining. Note that $n_{b}\geq n^{\prime}_{b}\geq n_{b}-\omega(n)$, so

The number of new neighbors of $x$ of type $b$ has a binomial $Bin(n^{\prime}_{b},K_{ab}/n)$ distribution, and the numbers for different $b$ are independent. The total variation distance between a binomial $Bin(n,p)$ distribution and the Poisson distribution with the same mean is at most p. Hence the total variation distance between the binomial distribution above and the Poisson distribution $Poi(K_{ab}n^{\prime}_{b}/n)$ is at most $K_{ab}/n=O(1/n)$. Also, by (20),

Since we perform at most $\omega(n)$ steps in the exploration, we may, with an error probability of $O(\omega(n)/n)=o(1)$, couple the exploration with two multi-type branching processes $\mathcal{B}((1-2\epsilon)K)$ and $\mathcal{B}((1+\epsilon)K)$ such that the first process always finds at most as many new vertices of each type as the exploration, and the second process finds at least as many. Consequently, for a vertex $x$ of type $a$,

Since $\omega(n)\rightarrow\infty$, by Lemma 9.5 of , we have $\rho_{\geq\omega(n)}(K;a)\rightarrow\rho(K;a)$ for every matrix or finitary kernel $K$, which parametrizes the offspring distribution of the branching process in the sense that the number of offsprings of type $b$ coming from a parent of type $a$ follows $Poi(K_{ab}\pi_{b})$ distribution. So we can rewrite (22) as

A2. proof of Lemma 4.7

We need to consider certain branching process expectations $\sigma(K)$ and $\sigma_{\geq k}(K)$ in place of $\rho(K)$ and $\rho_{\geq k}(K)$. In preparation for the proof, we shall relate $\zeta(K)$ to the branching process $\mathcal{B}_{K}$ via $\sigma(K)$. As before, we assume that $K$ is a kernel on $(\mathcal{S},\pi)$ with $K\in L^{1}$.

Let $A$ be a Poisson process on $\mathcal{S}$, with intensity given by a finite measure $\lambda$, so that $A$ is a random multi-set on $\mathcal{S}$. If $g$ is a bounded measurable function on multi-sets on $\mathcal{S}$, it is easy to see that

Let $B(x)$ denote the first generation of the branching process $\mathcal{B}_{K}(x)$. Thus $B(x)$ is given by a Poisson process on $\mathcal{S}$ with intensity $K(x,y)\pi_{x}$. Suppose that $\sum_{b}K_{ab}\pi_{b}<\infty$ for every $a=1,\ldots,Q$, so $B(x)$ is finite. Let $\sigma(K;x)$ denote the expectation of $|B(x)|\mathbf{1}[|\mathcal{B}_{K}(x)|=\infty]$, recalling that under the assumption $\sum_{b}K_{ab}\pi_{b}<\infty$ for every $a$, the branching process $\mathcal{B}_{K}(x)$ dies out if and only if $|\mathcal{B}_{K}(x)|<\infty$. Then

Here the penultimate step is from (24); the last step uses the fact that the branching process dies out if and only if none of the children of the initial particle survives. Writing $B$ for the first generation of $\mathcal{B}_{K}$ conditioned on survival becomes

Then, integrating over $x$ and subtracting from $\sum_{a,b}K_{ab}\pi_{a}\pi_{b}$, we get,

So, the kernel for the conditioned branching process becomes

A3. proof of Lemma 4.8

We have $\mathcal{S}$ is finite, say $\mathcal{S}=\{1,2,\ldots,Q\}$. Let $\Gamma_{d}(v)\equiv\Gamma_{d}(v,G_{n})$ denote the $d$-distance set of $v$ in $G_{n}$, i.e., the set of vertices of $G_{n}$ at graph distance exactly $d$ from $v$, and let $\Gamma_{\leq d}(v)\equiv\Gamma_{\leq d}(v,G_{n})$ denote the $d$-neighborhood $\cup_{d^{\prime}\leq d}\Gamma_{d^{\prime}}(v)$ of $v$.

Let $0<\varepsilon<1/10$ be arbitrary. The proof of (23) involved first showing that, for $n$ large enough, the neighborhood exploration process starting at a given vertex $v$ of $G_{n}$ with type $a$ (chosen without inspecting $G_{n}$) could be coupled with the branching process $\mathcal{B}_{(1+\varepsilon)K^{\prime}}(i)$, where the $K^{\prime}$ is defined by equation (26), so that the branching process is conditioned to survive. However, henceforth we shall abuse notation and denote $K^{\prime}$ as $K$.

The neighborhood exploration process and multi-type branching process can be coupled so that for every $d$, $|\Gamma_{d}(v)|$ is at most the number $N_{d}$ of particles in generation $d$ of $\mathcal{B}_{(1+2\varepsilon)K}(i)$. The number of vertices at generation $d$ of type $c$ of branching process $\mathcal{B}_{(1+2\varepsilon)K}(a)$, denoted by $N^{a}_{d,c}$ and the number of vertices of type $c$ at distance $d$ from $v$ for the neighborhood exploration process of $G_{n}$ is denoted by $|\Gamma^{a}_{d,c}(v)|$f, where, $c=1,\ldots,Q$.

Let $N^{a}_{t}(c)$ be the number of particles of type $c$ in the $t$-th generation of $\mathcal{B}_{K}(a)$, then, $N^{a}_{t}$ is the vector $(N^{a}_{t}(1),\ldots,N^{a}_{t}(Q))$. Also, let $\nu=(\nu_{1},\ldots,\nu_{Q})$ be the eigenvector of $T_{K}$ with eigenvalue $\lambda$ (unique, up to normalization, as $P$ is irreducible). From standard branching process results, we have

where $X\geq 0$ is a real-valued random variable, $X$ is continuous except that it has some mass at 0, and $X=0$ if and only if the branching process eventually dies out and lastly,

under the conditions given in Theorem V.6.1 and Theorem V.6.2 of .

Set $D=(1-10\varepsilon)\log(n/\nu_{a}\nu_{b})/\log\lambda$. Then $D<(1-\varepsilon)\log(n/\nu_{a}\nu_{b})/\log((1+2\varepsilon)\lambda)$ if $\varepsilon$ is small enough, which we shall assume. Thus,

A4. proof of Lemma 4.9

We consider the branching process conditioned on survival. Now, we consider the single type branching process with offspring distribution $Poi(K_{aa}\pi_{a})$ and the corresponding stochastic block model graph $G^{\prime}_{n}$, is the induced subgraph of the original graph $G_{n}$, where, vertices of $G^{\prime}_{n}$ are only the vertices of type $a$ from $G_{n}$. So, $G^{\prime}_{n}$ has in total $n_{a}$ vertices. So, we can always upper bound the the distance between two vertices of same type in $G_{n}$, by the distance between the two vertices in $G^{\prime}_{n}$, since, the path representing distance between two vertices in $G^{\prime}_{n}$ is present in $G_{n}$ but, the converse is not true. So, distance between two vertices in $G_{n}$ is always less than distance between two vertices in $G^{\prime}_{n}$. So, we can say for any $v,w\in V(G_{n})orV(G^{\prime}_{n})$ of same type,

From here on, we shall abuse notation a bit and call $G^{\prime}_{n}$ as $G_{n}$, since we are only considering the graph $G^{\prime}_{n}$ from here on as the graph from stochastic block model.

We have $K_{aa}>0$. Fix $0<\eta<1/10$. We shall assume that $\eta$ is small enough that $(1-2\eta)K_{aa}\pi_{a}>1$. In the argument leading to (23) in proof of Lemma 4.6, we showed that, given $\omega(n)$ with $\omega(n)=o(n)$ and a vertex $v$ of type $a$, the neighborhood exploration process of $v$ in $G_{n}$ could be coupled with the branching process $\mathcal{B}_{(1-2\eta)K_{aa}}(a)$ so that whp the former dominates until it reaches size $\omega(n)$.

From here onwards we shall only consider a single-type branching process where particles have type $a$. More precisely, writing $N_{d,a}$ for the number of vertices of type $a$ in generation $d$ of $\mathcal{B}_{(1-2\eta)K_{aa}}(a)$, and $\Gamma_{d,a}(v)$ for the set of type-$a$ vertices at graph distance $d$ from $v$, whp

This relation between the number of vertices at generation $d$ of branching process $\mathcal{B}_{(1-2\eta)K_{aa}}(a)$, denoted by $N_{d,a}$ and the number of vertices at distance $d$ from $v$ for the neighborhood exploration process of $G_{n}$, denoted by $|\Gamma_{d,a}(v)|$ becomes highly important later on in this proof. Note that the relation only holds when $|\Gamma_{\leq d}(v)|<\omega(n)$ for some $\omega(n)$ such that $\omega(n)/n\rightarrow 0$ as $n\rightarrow\infty$.

Now let us begin the second part of the proof. Let $N_{t}(a)$ be the number of particles of type $a$ in the $t$-th generation of $\mathcal{B}_{K}$. Also, let $\lambda_{a}=K_{aa}\pi_{a}$. From standard branching process results, we have

where $X\geq 0$ is a real-valued random variable, $X$ is continuous except that it has some mass at 0, and $X=0$ if and only if the branching process eventually dies out.

Now, we have conditioned that the branching process with kernel $K_{aa}$ is conditioned to survive. The right-hand side tends to $\rho(K_{aa})=1$ as $\eta\rightarrow 0$. Hence, given any fixed $\gamma>0$, if we choose $\eta>0$ small enough we have

Now, the neighborhood exploration process and branching process can be coupled so that for every $d$, $|\Gamma_{d}(v)|$ is at most the number $M_{d}$ of particles in generation $d$ of $\mathcal{B}_{(1+2\varepsilon)K_{aa}}(a)$ from Lemma 4.6 and Eq (21). So, we have,

if $\eta$ is small enough, since $D$ be the integer part of $\log((n\pi_{a})^{1/2+2\eta})/\log((1-2\eta)\lambda_{a})$ and $|n_{a}/n-\pi_{a}|<\varepsilon$. Note that the power $2/3$ here is arbitrary, we could have any power in the range $(1/2,1)$. Hence,

and whp the coupling described in (28) extends at least to the $D$-neighborhood. So, now, we are in a position to apply Eq (28), as we have $|\Gamma_{\leq D}(v)|\leq n_{a}^{2/3}<\omega(n)$, with $\omega(n)/n\rightarrow 0$.

Now let $v$ and $w$ be two fixed vertices of $G(n_{a},P_{a})$, of type $a$. We explore both their neighborhoods at the same time, stopping either when we reach distance $D$ in both neighborhoods, or we find an edge from one to the other, in which case $v$ and $w$ are within graph distance $2D+1$. We consider two independent branching processes $\mathcal{B}_{(1-2\eta)K_{aa}}(a)$, $\mathcal{B}^{\prime}_{(1-2\eta)K_{aa}}(a)$, with $N_{d,a}$ and $N^{\prime}_{d,a}$ vertices of type $a$ in generation $d$ respectively. By previous equation, whp we encounter $o(n)$ vertices in the explorations so, by the argument leading to (28), whp either the explorations meet, or $|\Gamma_{D,a}(v)|\geq N_{D,a}$ and $|\Gamma_{D,a}(w)|\geq N^{\prime}_{D,a}$ with the explorations not meeting. Using bound on $N_{d,a}$ and the independence of the branching processes, it follows that