Stochastic graph Voronoi tessellation reveals community structure

Given a network, the statistical ensemble of its graph-Voronoi diagrams with randomly chosen cell centers exhibits properties convertible into information on the network's large scale structures. We define a node-pair level measure called Voronoi cohesion which describes the probability for sharing the same Voronoi cell, when randomly choosing $g$ centers in the network. This measure provides information based on the global context (the network in its entirety), a type of information that is not carried by other similarity measures. We explore the mathematical background of this phenomenon and several of its potential applications. A special focus is laid on the possibilities and limitations pertaining to the exploitation of the phenomenon for community detection purposes.

Figure 1

Voronoi tessellation in Euclidean space and on graphs. (a) Voronoi diagram in 2D Euclidean space. (b) Illustration of network clustering with Voronoi diagrams. Layout created by the graph drawing application Gephi using the ForceAtlas2 layout algorithm [24]. Seeds (generators) appear as black dots. Colors indicate different Voronoi cells, in this case also corresponding well to communities.

Figure 2

First glance at stochastic graph Voronoi tessellation. Subfigures show how the Voronoi cohesion map for a twelve node graph would be calculated from an ensemble of $R$ tessellations. The two generator nodes, e.g., (1, 5), (2, 7),..., (5, 10), are picked randomly producing an ensemble of binary colocation matrices [one (white) for same cell, zero (black) for different cell node pairs]. The ensemble average of the colocation matrices yields the cohesion map, i.e., probabilities for any node pair to share the same Voronoi cell (lighter squares represent higher probabilities; see color bar).

Figure 3

Cohesion map for an undirected and unweighted benchmark network of $N=500$ nodes and $M=7454$ edges organized into 10 first level and 28 second level communities [17, 18] (lighter squares represent higher probabilities; see color bar in Fig. 2).

Figure 4

Dependence of intra- and intermodular cohesion ratio $c_{11}/c_{12}$ on the number of generator nodes for the case of a two-module network of extreme modularity. (a) Simulation results for an extremely modular network of size $N=2\times 250$ with $m=2$ ER-type modules, with intra- and intermodule link densities of $q=0.5$ and $b={10}^{-4}$, respectively. Voronoi cohesion matrices were estimated for three different ensemble sizes (repeats) ($R=100,500$, and 5000). The analytical results expressed by Eqs. (8) and (11) are represented as continuous black line. (b),(c),(d) Dependence of sensitivity $[c_{\text{intra}}$ from Eq. (7)], specificity $[1-c_{\text{inter}}$ from Eq. (10)], and accuracy $[(c_{\text{intra}}-c_{\text{inter}}+1)/2]$ on generator size and module number [20]. Lighter colors represent higher values.

Figure 5

Study of Voronoi cohesion for a network of two equally large ER-type modules ($m=2$) with noninfinitesimal intermodular link density, $b$. There is one generator placed into each of the modules ($g=2$). (a) Illustration of how the two modules are shared between the two Voronoi cells as a function of the distance to the generators. The link densities in the two modules are $q_1$ and $q_2$, respectively. Areas covered by flatly colored and dotted secondary rectangles represent “regions” with nodes at unit distance (one step away) from generator one and two, respectively. Remaining areas represent nodes that are at distance two from both generators. (b) Influence of the intra-, $q_1=q_2=q$, and intermodular densities, $b$, on the relative “area” of cell 1 in module 1 [see Eq. (13)]. (c) The corresponding contrast calculated from Eq. (16). (d),(e) Intra- and intermodular Voronoi cohesion as a function of the intermodular link density, $b$. Analytical results expressed in Eqs. (14) and (15) are compared to simulation for several intramodular link densities, $q$. Simulation data was obtained from an ensemble of 5000 tessellations (10 topologies $\times$ 500 generator sets) of a network of $N=2\times 800$ nodes. Most error bars representing standard error lay within the markers.

Figure 6

Simulation study of the effect of network size, $N$, number of ER-type modules, $m$, and the number of seeds (generators), $g$. Intra- and intermodular link densities are set to $q=0.5$ and $b=0.05$, respectively. (a) Statistical ensemble size (number of iterations) necessary to keep the estimation error of the cohesion below a fixed tolerance threshold of $5\times {10}^{-4}$ [see Eq. (18)]. (b) Contrast defined in Eq. (19). The ruined cohesion picture (see insets) at large seed numbers confirms the conclusions of Sec. 3a and demonstrates the unsuitability of contrast as defined in Eqs. (3) and (19) for situations when Voronoi cells are small. (c) Relative contrast defined in Eq. (20).

Figure 7

(a) Cohesion histogram for all node pairs in the cohesion map of an $m=9$ module undirected and unweighted benchmark network: $N=500, M=5000, g=15$, and $R=3000$ [17, 18]. Intra- and intermodular pairs are identified and colored based on truth information. The cohesion and internode distance matrices are presented as insets with lighter colors corresponding to higher values. (b) Cohesion histogram for the same network using the contrast boosting technique discussed in Sec. 5.

Figure 8

Network of American political blogs (POLBLOGS) separated into two communities referred to as 1 [violet (darker gray)] and 2 [orange (lighter gray)] by the edge relocation method described in Sec. 5. (a) The representation of the network in Gephi using the ForceAtlas2 layout algorithm [24]. All edges are assumed to have unit length. (b),(c) Voronoi cohesion matrix and histogram obtained without contrast boost and with the edge relocation methods, respectively (see Sec. 5). (d) Average cohesion vs average distance for each node. By average cohesion(distance) of a node we mean the arithmetic mean of the cohesion (distance) matrix elements in the row corresponding to the node but limited to one of the two groups. Magenta circles (green triangles) represent the average cohesion and distance of a node in group 1(2) to its own group. Orange squares correspond to the same quantities but in relation to the opposite group. (e) Average cohesion of a node to group 1 vs the same quantity for group 2. Each node appears as a point colored by its group affiliation (red triangle or blue circle).

Figure 9

Influence of the number of seeds exemplified on a small social network (Zachary's karate club) [27]. The layout is generated using the LGL network visualization method [28] as implemented in the iGraph software package [29]. Statistical errors are eliminated by considering all possible Voronoi diagrams. (a),(c) Topology and modular structure according to the GANXiS [25] and Louvain [26] algorithms. (b),(d) Voronoi cohesion maps for $g=2$ seeds. Node ordering is based on the two clusterizations. (e) Modular structure established visually based on the Voronoi cohesion map. Starting from the map in (b) nodes were rearranged manually so that block diagonality was improved yielding the map in the top-left tile in (g). (f) Dependence of the relative contrast [see Eq. (20)] on the number of seeds. As replacement for truth information the GANXiS clusterization is used [see (a)]. (g) Cohesion matrices for different numbers of seeds. Values range from 0 (black) to 1 (white). Nodes are ordered as described in (e). Seed numbers are indicated in the top-right corner of each map.

Figure 10

Neural network of the Caenorhabditis elegans. Voronoi cohesion matrix and histogram yielded by the (a) plain (no contrast boosting) and the (b) edge relocation methods, respectively. We can observe a correction in the contrast of the cohesion matrix in (b) compared to (a) (see insets), but the histograms show that very little difference was achieved in terms of separating the inter- and intrapairs. Surrogate truth information (see the Appendix) was provided by the Louvain clusterization method [26]. Node ordering in the two insets is also based on this information.