In this paper, i will give a summary about the article A nonparametric view of network models and Newman – Girvan and other modularities written by Peter J. Bickela and Aiyou Chen \cite{nonp}.

The purpose is to identificate community structure in a network, where we look at networks as a set of vertices with connections among them, and vertices whitin a community have the same densities of connecting with vertices in their own community as well as different ones with other communities. The analysis is asymptotic, insofar the number of vertices go to infinity. The networks can be described by parametric models, the so called blockmodels, as follows.

There are ${K}$ unknown subcommunities. The connections among the vertices are represented by undirected edges. This gives us an undirected graph and the corresponding adjacency matrix ${\{A_{ij} : i,j\ge 1\}}$ with the following properties.

1. Individuals independently belong to community ${j}$ with probability ${\pi_j ,\, 1\le j\le K ,}$ ${\sum_{j=1}^K \pi_j = 1.}$
2. If an individual ${i}$ belongs to the community ${a}$, then the probability of ${i}$ is in connection with the individual ${j}$ from the community ${b}$ is ${P_{ab}}$. This gives a symmetric ${K\, \times \, K}$ matrix ${\{P_{kl}\, : \, 1\le k,l\le K\}}$ of probabilities.

— Newman–Girvan and Likelihood Modularities —

In order to find the ${K}$ communities we have to give an assignment for the vertices ${\mathbf e\equiv \{e_1,...,e_n\}}$ where ${e_j\in\{1,...,K\}}$. In the case of an observed graph ${\mathbf{c} = (c_1,...,c_n) }$ is a realization of ${n}$ independent ${Multinomial(1,n)}$ variables. To measure the adequacy of an assignment we can use the matrix

$\displaystyle R(\mathbf c,\mathbf e) = \{\mathbf R_{ab} : 1\le a,b\le K\},$

where ${\mathbf R_{ab} = \frac{1}{n} \sum_{i=1}^n I(c_i=b,e_i=a)}$. If ${\mathbf e = \mathbf c}$ we would get

$\displaystyle R(\mathbf c,\mathbf e) = diag(\mathbf f(\mathbf c))$

where ${\mathbf f_a(\mathbf e) = \frac{1}{n} n_a(\mathbf e)}$ and ${n_a(\mathbf e) = \sum_{i=1}^n I(e_i = a)}$. In the definition of the Newman-Girvan modularity we use the following quantities.

$\displaystyle O_{kl}(\mathbf e,A) = \sum_{1\le i,j\le n}A_{ij}I(e_i=k,e_j=l)$

It can be seen, that ${O_{kk}}$ is twice the number of edges among the members of the ${k}$-th community. Let ${D_k(\mathbf e,A) = \sum_{i=1}^K O_{ki}}$, so ${D_k}$ is the sum of degrees in the ${k}$-th community. Let ${L = \sum_{i=1}^K D_i}$, so ${L}$ is twice the number of edges in the network. Now we can define the Newman-Girvan modularity as

$\displaystyle Q_{NG}(\mathbf e,A) = \sum_{i=1}^K\frac{O_{kk}}{L}-\left(\frac{D_k}{L}\right)^2.$

The Newman-Girvan algorithm searches for the assignment vector ${\hat{\mathbf c}}$ that maximizes ${Q_{NG}}$. To express this in a shorter form we define ${\hat{\mathbf c}}$ as

$\displaystyle \hat{\mathbf c} = \arg\, \max Q_{NG}(\mathbf e,A).$

The other studied modularity is the likelihood modularity, which we get by maximizing the log-likelihood of ${A}$ over ${P}$.

$\displaystyle Q_{LM}(\mathbf e,A)=\frac{1}{2}\sum_{a,b}n_{ab}\tau \left(\frac{O_{ab}}{n_{ab}}\right),$

where ${n_{ab}=n_an_b}$ if ${a\neq b}$, ${n_{aa}=n_a(n_a-1)}$, and ${\tau(x) = x\log x+(1-x)\log (1-x)}$.

In general we think of modularities in the form,

$\displaystyle Q(\mathbf e, A) = F_n\left( \frac{O}{\mu_n},\frac{L}{\mu_n},f(\mathbf e)\right)$

where ${\mu_n = E(L)}$, and ${O}$ is the matrix ${\{O_{ab}(\mathbf e,A)\,:\, 1\le a,b\le K\}}$, and ${F_n}$ is a real valued function. We will give conditions under which the assignment is consistent. The consistency of a sequance of assignments ${\hat{\mathbf c}}$ means that

$\displaystyle \mathbb{P}[\hat{\mathbf c} = \mathbf c]\rightarrow 1,\qquad \textrm{as } n\rightarrow \infty.$

It can be seen that

$\displaystyle \frac{\mathbb{E}(O(\mathbf e,A)|\mathbf c)}{E(L)} = R(\mathbf c,\mathbf e)SR^T(\mathbf c,\mathbf e)$

where ${S_{ab}=\frac{1}{\rho_n}\mathbb{P}(A_{12}=1|c_1=a,c_2=b)}$.

We assume that ${F_n}$ can be approximated with a function ${F(RSR^T,1,\mathbf f(\mathbf e))}$. We also assume first that ${F_n\equiv F}$. Let ${\lambda_n \equiv \mathbb{E}(Degree).}$ We need the following conditions.

1. ${\mathbf c}$ with ${\mathbf f(\mathbf c)=\pi}$ is the right assignment for the limiting problem.
2. ${S}$ does not have two identical columns, and ${\pi_i > 0, i\in \{1,...,K\}.}$
3. The third condition contains technical conditions.

Suppose ${F,S}$ and ${\pi}$ satisfy 1-3 and ${\hat{\mathbf c} = \arg\, \max Q(\mathbf e,A)}$. Suppose ${\frac{\lambda_n}{\log n}\rightarrow \infty}$. Then,

$\displaystyle \limsup_{n\rightarrow \infty} \frac{\log \mathbb{P}(\hat{\mathbf c} \neq \mathbf c)}{\lambda_n} < 0.$

It can be shown that the likelihood modularity is always consistent, but the Newman-Girvan is not.

— Simulation —

To perform an empirical comparison of Newman-Girvan, likelihood modularities and spectral clustering,where ${K=3}$, random matrices were generated and the ${Q_{NG},Q_{LM}}$ modularities were maximized on them. The percent of incorrect labeling was plotted depending on the average node degree.

\leavevmode \includegraphics[width=0.7\textwidth]{simu.png}

\caption{Empirical comparison} On figure 0 we can see that the likelihood method gives much less incorrect labeling than Newman-Girvan and spectral clustering.

— Data example —

The L-M and N-G modularity algorithms were also compared with applications to real data sets. One of them was Zachary’s Karate Club Network, which is often used to test community detection algorithms. In this network the edges mean friendship among the members of the karate club. Shortly after the observation of the friendships the club split into two disjoint parts as a result of internal agreement. This is marked whit a dashed line on the figure. The left side of figure 0 shows the result given by the likelihood algorithm, and the right side shows the result given by the N-G algorithm. The shapes of the nodes give the assignment for the vertices.

\leavevmode \includegraphics[width=0.8\textwidth]{karate.png}

\caption{Zachary’s karate club network}

{9} \bibitem{nonp} Peter J. Bickel, Aiyou Chen: A nonparametric view of network models and Newman-Girvan and other modularities, Proceedings of the National Academy of Sciences, Vol. 106, No. 50. (15 December 2009), pp. 21068-21073.

Reklámok