###### Abstract

Nearest neighbor search is a basic computational tool used extensively in
almost research domains of computer science specially when dealing with large
amount of data. However, the use of nearest neighbor search is restricted for
the purpose of algorithmic development by the existence of the notion of
nearness among the data points. The recent trend of research is on large,
complex networks and their structural analysis, where nodes represent entities
and edges represent any kind of relation between entities. Community detection
in complex network is an important problem of much interest. In general, a
community detection algorithm represents an objective function and captures
the communities by optimizing it to extract the interesting communities for
the user. In this article, we have studied the nearest neighbor search problem
in complex network via the development of a suitable notion of nearness.
Initially, we have studied and analyzed the exact nearest neighbor search
using metric tree on proposed metric space constructed from complex network.
After, the approximate nearest neighbor search problem is studied using
locality sensitive hashing. For evaluation of the proposed nearest neighbor
search on complex network we applied it in community detection problem. The
results obtained using our methods are very competitive with most of the well
known algorithms exists in the literature and this is verified on collection
of real networks. On the other-hand, it can be observed that time taken by our
algorithm is quite less compared to popular methods.

###### keywords:

Complex Network; Nearest Neighbor; Metric tree; Locality Sensitive Hashing;
Community Detection

10.3390/—— xx Received: xx / Accepted: xx / Published: xx Nearest Neighbor
search in Complex Network for Community Detection Suman Saha 1,* and S.P.
Ghrera 1<EMAIL_ADDRESS>
##  1 Introduction

Nearest neighbor (NN) search is an important computational primitive for
structural analysis of data and other query retrieval purposes. NN search is
very useful for dealing with massive datasets, but it suffer with "curse of
dimensionality"Uhlmann (1991); Ruiz (1986). However, some recent surge of
results show that it is also very efficeint for high dimensional data provided
a suitable space partitioning data structure is used, like, kd-tree, quad-
tree, R-tree, metric-tree and locality sensitive hashingPanigrahy (2006);
Indyk and Motwani (1998); Gionis et al. (1999); Dasgupta and Freund (2008).
Some of these data structures also support approximate nearest neighbor search
which hardly made any degradation of results whereas saves lot of
computational times. In the NN-search problem, the goal is to pre-process a
set of data points, so that later, given a query point, one can find
efficiently the data point nearest to the query point on some metric space of
consideration. NN search has many applications in data processing and
analysis. For instance, information retrieval, searching image databases,
finding duplicate pages, compression, and many others. To represent the
objects and the similarity measures, one often uses geometric notions of
nearness Akoglu et al. (2014); Liu et al. (2004).

One important research direction of recent interest is to extract network
communities in large real graphs such as social networks, web, collaboration
networks and bio-networks Freeman (1978); Carrington et al. (2005); Newman
(2003); Radicchi et al. (2004). The availability of large, detailed datasets
representing such networks has stimulated extensive study of their basic
properties, and the identification of hirarchical structural featuresNewman
(2003); Fortunato (2010). Other than graphs, the complex networks are
characterized by small average path length and high clustering coefficient. A
network community (also known as a module or cluster) is typically a group of
nodes with more interconnections among its members than the remaining part of
the network Weiss and Jacobson (1955); Schaeffer (2007); Fortunato (2010). To
extract such group of nodes from a network one generally selects an objective
function that captures the possible communities as a set of nodes with better
internal connectivity than external Newman and Girvan (2004); Luxburg (2007).
However, very less research is done for network community detection which
tries to develop nearness among the nodes of a complex network and use nearest
neighbor search for partitioning the networkPons and Latapy (2004); Duch and
Arenas (2005); Chakrabarti (2004); Macropol and Singh (2010); Levorato and
Petermann (2011); Brandes et al. (2003); Bullmore and Sporns (2009). Complex
networks are characterized by small average path length and high clustering
coefficient the way the metric is defined should be able to capture the
crucial properties of complex networks. Therefore, we need to create the
metric very carefully so that it can explore the underlying community
structure of the real life networksSaha and Ghrera (2015).

In this work, we have developed the notion of nearness among the nodes of the
network using some new matrices derived from modified adjacency matrix of the
graph which is flexible over the networks and can be tuned to enhance the
structural properties of the network required for community detection. The
main contributions of this work include:

  * •

Define a metric on complex network suitable for community detection

  * •

Choice of data structure and approximations for NN computation (M-tree, LSH)

  * •

Community detection algorithm developed using NN search

  * •

Experiments on real networks

The rest of this paper is organized as follows:In Section 2 several
definitions and challanges relevent to nearest neighbor search in complex
network are discussed. Section 3 describes the notion of nearness in complex
network and developed a method to represent a complex network as points of a
metric space. Section 4 describes the problem of nearest neighbor search over
complex network and the use of metric tree data structure in this regard. In
Section 5, the problem approximate nearest neighbor search on complex network
is discussed with a newly developed locality sensitive hashing method. Network
community detection using exaxt and approximate nearest neighbor search is
formulated and several possible solutions are presented in Section 6, also,
the initialization procedures, termination criteria, convergence are discussed
in detail. The results of comparison between community detection algorithms
are illustrated in Section 7. The computational aspects of the proposed
framework are also discussed in this section.

##  2 NNSCN: Nearest neighbor search on complex network

The nearest-neighbor searching problem is to find the nearest points in a $D$
dimensional dataset $X\subset R^{D}$ containing $n$ points to a query point
$q\in R^{D}$ , usually in a metric space. It has applications in a wide range
of real-world settings, in particular pattern recognition, machine learning
and database querying to name a few. Several effective methods exist for this
problem when the dimension $D$ is small, such as Voronoi diagrams, however,
kd-trees and metric trees are common when the dimension is high. Many methods
with different approach are developed for searching data and finding the
nearest point. Searching the nearest neighbor in different studies are
presented by different names such as post office problem, proximity search,
closest point search, best match file searching problem, index for similarity
search, vector quantization encoder, the light-bulb problem and etc.. The
solutions for the Nearest Neighbor Search (NNS) problem usually have two
parts: nearness determination in the data and and algorithmic developments. In
most the NNS algorithms, the main framework is based on four fundamental
algorithmic ideas: Branch-and-bound, Walks, Mapping-based techniques and
Epsilon nets. There are thousands of possible framework variations and any
practical application can lead to its unique problem formalization such as
pattern recognition, searching in multimedia data, data compression,
computational statistics, information retrieval, databases and data mining,
machine learning, algorithmic theory, computational geometry, recommendation
systems and etc.

###  2.1 NN problem definition on complex network

A NNS problem defined in a metric space is defined below.

######  Definition 1 (Metric space).

Given a set $S$ of points and $d$ as a function to compute the distance
between two points. Pair $(S,d)$ distinguished metric space if $d$ satisfies
reflexivity, non-negativity, symmetry and triangle inequality.

Non-metric space data are indexed by special data structures in non-metric
spaces and then searching is done on these indexes. A few efficient methods
exist for searching in non- metric space that in most of them, non-metric
space is converted to metric space. The focus of this paper is on the problems
defined on a metric space. In a more detailed classification, NNS problems can
be defined in Euclidean space as follow:

######  Definition 2 (Nearest neighbor search).

Given a set $S$ of points in a $D$ dimensional space, construct a data
structure which given any query point finds the point in $S$ with the smallest
distance with $q$.

This definition for a small dataset with low dimension has sub linear (or even
logarithmic) query time, but for massive dataset with high dimension is
exponential. Fortunately, some little approximation can decrease the
exponential complexity into polynomial time.

Approximate NNS is defined as:

######  Definition 3 (Approximate nearest neighbor).

Given a set $S$ of Points in a $D$-dimensional space, construct a data
structure which given any query point, reports any point within distance at
most $c$ times the nearest distance from $q$.

The first requirement in order to search in a metric space is the existence of
a formula to calculate the distance between each pair of objects in $S$.
Different metric distance functions can be defined depending on the search
space of consideration. A NN query on a complex network G, consists of a
source node $s$ and a metric function $d(x,y)$. This computations depends on
the dimension of the instance and face "curse of dimensionality" problem. The
computation can be reduced drastically if instead of computing the exact
nearest neighbor we compute the approximate nearest neighbor.

##  3 Notion of nearness in complex network

The notion of nearness among the nodes of a graph are used in several purposes
in the history fo literature of graph theory. Most of the time the shortest
path and edge connectivity are popular choice to describe nearness of nodes.
However, that edges do not give the true measure of network connectivity
(proof by kleinbarg). The notion of network connectivity some times
generalized to be the number of paths, of any length, that exist between two
nodes. This measure, called influence by sociologists, because it measures the
ability of one node to affect another, gives a better measure of connectivity
between nodes of real life graphs / complex networks. Beside discovering
natural groups within a network, the influence metric can also help identify
the weak ties who bridge different communities. Research in this direction
gained special attention in the domain of complex network analysis, some of
them along with the one proposed in this article are discussed in the
following subsections.

###  3.1 Nearness literature

Methods based on node neighborhoods. For a node $x$, let $N(x)$ denote the set
of neighbors of $x$ in a graph $G(V,E)$ . A number of approaches are based on
the idea that two nodes $x$ and $y$ are more likely to be affected by one
another if their sets of neighbors $N(x)$ and $N(y)$ have large overlap.

Common neighbors: The most direct implementation of this idea for nearness
computation is to define $d(x,y):=|N(x)\cap N(y)|$, the number of neighbors
that $x$ and $y$ have in common.

Jaccard coefficient: The Jaccard coefficient, a commonly used similarity
metric, measures the probability that both $x$ and $y$ have a feature $f$ ,
for a randomly selected feature $f$ that either $x$ or $y$ has. If we take
features here to be neighbors in $G(V,E)$ , this leads to the measure
$d(x,y):=|N(x)\cap N(y)|/|N(x)\cup N(y)|$.

Preferential attachment:The probability that a new edge involves node $x$ is
proportional to $|N(x)|$, the current number of neighbors of $x$. The
probability of co-authorship of $x$ and $y$ is correlated with the product of
the number of collaborators of $x$ and $y$. This corresponds to the measure
$d(x,y):=|N(x)|\times|N(y)|$.

Katz measure: This measure directly sums over the collection of paths,
exponentially damped by length to count short paths more heavily. This leads
to the measure $d(x,y):=\beta\times|paths(x,y)|$ where $paths(x,y)$ is the set
of all length paths from $x$ to $y$. ($\beta$ determines the path size, since
paths of length three or more contribute very little to the summation.)

Hitting time and PageRank: A random walk on $G$ starts at a node $x$, and
iteratively moves to a neighbor of $x$ chosen uniformly at random. The hitting
time $Hx,y$ from $x$ to $y$ is the expected number of steps required for a
random walk starting at $x$ to reach $y$. Since the hitting time is not in
general symmetric, it is also natural to consider the commute time
$C(x,y):=H(x,y)+H(y,x)$. Both of these measures serve as natural proximity
measures, and hence (negated) can be used as $d(x,y)$. Random resets form the
basis of the PageRank measure for Web pages, and we can adapt it for link
prediction as follows: Define $d(x,y)$ to be the stationary probability of $y$
in a random walk that returns to $x$ with probability $\alpha$ each step,
moving to a random neighbor with probability $1-\alpha$.

Most of the methods are developed for different types of problems like
information retrieval, ranking, prediction e.t.c. and developed for general
graphs. In this article we studied a measure specially designed for complex
network and discussed in the next subsection

###  3.2 Proposed metric on complex network

In this section we have demonstrated the procedure to transform a graph into
points of a metric space and developed the methods of community detection with
the help of metric defined for pair of points. We have also studied and
analyzed the community structure of the network therein.

The nodes of the graph do not lie on a metric space. The standard Euclidean
distance and spherical distance define over the adjacency or Laplacian
matrices above failed to capture similarity information among the nodes of a
complex network. On the other-hand, the algorithms developed based on shortest
path or Jaccard similarity are computationally inefficient and have less
success in terms of standard evaluation criteria(like, conductance and
modularity).

In this work, we have tried to develop the notion of similarity among the
nodes using some new matrices derived from adjacency matrix and degree matrix
of the graph. Let $A$ be the adjacency matrix and $D$ the degree matrix of the
graph $G=(V,E)$. The Laplacian $L=D-A$. We have defined two diagonal matrix of
same size $D(\lambda)$ and $D(\lambda_{x})$ where $\lambda$ is a parameter
determine from the given graph and can be optimized from the optimization
criteria of the problem under consideration. In $D(\lambda)$ a fixed optimally
determine value is used in the diagonal entries of the matrix $D$ and in
$D(\lambda_{x})$ a variable value also optimally determine is used in the
diagonal entries of the matrix $D$. The similarities are defined on matrices
$L_{1}$ and $L_{2}$, where $L_{1}=D(\lambda)+A$ and $L_{2}=D(\lambda_{x})+A$
respectively as spherical similarity among the rows and determine by applying
a concave function $\phi$ over the standard notions of similarities like,
Pearson coefficient($\sigma_{PC}$), Spacerman coefficient($\sigma_{SC}$) or
Cosine similarity($\sigma_{CS}$). $\phi(\sigma)()$ must be chosen using the
chord condition to obtain a metric.

In this subsection we have demonstrated the algorithm to convert the nodes of
the graph to the points of a metric space preserving the community structure
of the graph. The algorithm depends on the sub modules 1) construction of
$L_{x}$ ($L_{1}$ or $L_{2}$) and 2) obtaining a structure preserving distance
function. The algorithm works as picking pair of nodes from $L_{x}$ and and
computing distance defined in the second module.

####  3.2.1 $L_{x}$ construction

The $L_{1}$ is defined as $L_{1}=D(\lambda)+A$, where $A$ is the adjacency
matrix of the given network and $D(\lambda)$ is a diagonal matrix of same size
with diagonal values equal to a non negative constant $\lambda$.

The $L_{2}$ is defined as $L_{2}=D(\lambda_{x})+A$, where $A$ is the adjacency
matrix of the given network and $D(\lambda_{x})$ is a diagonal matrix of same
size with diagonal values determine by a non negative function $\lambda_{x}$
of the node $x$.

The choice of $\lambda$ and $\lambda_{x}$ plays a crucial role in combination
with the function chosen in the second module for determination of a suitable
metric and is discussed later part of this subsection.

####  3.2.2 Function selection

The function selection module determine the metric for pair of nodes. The
function selector $\phi$ converts a similarity function (Pearson
coefficient($\sigma_{PC}$), Spacerman coefficient($\sigma_{SC}$) or Cosine
similarity($\sigma_{CS}$)) into a distance matrix. In general the similarity
function satisfies the positivity and similarity condition of metric but not
triangle inequality. $\phi$ is a metric preserving
($\phi(d(x_{i},x_{j})=d_{\phi}(x_{i},x_{j})$), concave and monotonically
increasing function. The three conditions above refer to as chord condition.
The $\phi$ function is chosen to have minimum internal area with chord.

####  3.2.3 Choice of $\lambda$ and $\phi(\sigma)()$

The choices in the above sub modules play a crucial role in the graph to
metric transformation algorithm to be used for community detection. The
complex network is characterized by small average diameter and high clustering
coefficient. Several studies on network structure analysis reveal that there
are hub nodes and local nodes characterizing the interesting structure of the
complex network. Suppose we have taken $\phi=arccos$, $\sigma_{CS}$ and
constant $\lambda\geq 0$. $\lambda=0$ penalize the effect of direct edge in
the metric and is suitable to extract communities from highly dense graph.
$\lambda=1$ place the similar weight of direct edge and common neighbor reduce
the effect of direct edge in the metric and is suitable to extract communities
from moderately dense graph. $\lambda=2$ set more importance to direct edge
than common neighbor (this is the common case of available real networks).
$\lambda\geq 2$ penalize the effect of common neighbor in the metric and is
suitable to extract communities from very sparse graph. The choice of
$\lambda$ depends on the input graph, i.e. whether it is sparse or dense and
its cluster structure. A more detailed explanation on the metric described
above can be obtained in Saha and Ghrera (2015).

##  4 Nearest neighbor search on complex network using metric tree

There are a large number of methods developed to compute nearest neighbor
search. However, finding nearest neighbor search on some data where dimension
is high suffer from curse of dimensionality. Some recent research on this
direction revealed that dimension constrained can be tackled by using
efficient data structures like metric tree and locality sensitive hashing. In
this section we have explored metric tree to perform nearest neighbor search
on complex network with the help of metric mapping of complex network
described in the previous section.

###  4.1 Metric-tree

A metric tree is a data structure specially designed to perform nearest
neighbor query for the points residing on a metric space and perform well on
high dimension particularly when some approximation is permitted. A metric
tree organizes a set of points in a spatial hierarchical manner. It is a
binary tree whose nodes represent a set of points. The root node represents
all points, and the points represented by an internal node $v$ is partitioned
into two subsets, represented by its two children. Formally, if we use $N(v)$
to denote the set of points represented by node $v$, and use $v.lc$ and $v.rc$
to denote the left child and the right child of node $v$, then we have
$N(v)=N(v.lc)\cup N(v.rc)$ $\phi=N(v.lc)\cap N(v.rc)$ for all the non-leaf
nodes. At the lowest level, each leaf node contains very few points.

An M-Tree Ciaccia et al. (1997) has these components and sub-components:

  * •

Non-leaf nodes: A set of routing objects $N_{RO}$, Pointer to Node’s parent
object $v_{p}$.

  * •

Leaf nodes: A set of objects $N_{v}$, Pointer to Node’s parent object $v_{p}$.

  * •

Routing Object: (Feature value of) routing object $v_{r}$, Covering radius
$r(v_{r})$, Pointer to covering tree $T(v_{r})$, Distance of $v_{r}$ from its
parent object $d(v_{r},P(v_{r}))$

  * •

Object: (Feature value of the) object $v_{j}$, Object identifier oid$(v_{j})$,
Distance of $v_{j}$ from its parent object $d(v_{j},P(v_{j}))$

Partitioning: The key to building a metric-tree is how to partition a node v.
A typical way is as follows: We first choose two pivot points from $N(v)$,
denoted as $v.lpv$ and $v.rpv$. Ideally, $v.lpv$ and $v.rpv$ are chosen so
that the distance between them is the largest of all distances within $N(v)$.
More specifically, $||v.lpv-v.rpv||=max_{p_{1},p_{2}\in N(v)}||p_{1}-p_{2}||$.
However, it takes $O(n^{2})$ time to find the optimal $v.lpv$ and $v.rpv$. In
practice a linear-time heuristic is used to find reasonable pivot points.
$v.lpv$ and $v.rpv$ are then used to partition node $v$. We first project all
the points down to the vector $u=v.rpv-v.lpv$, and then find the median point
A along $u$. Next, we assign all the points projected to the left of A to
$v.lc$, and all the points projected to the right of $A$ to $v.rc$. We use $L$
to denote the $d-1$ dimensional plane orthogonal to $u$ and goes through $A$.
It is known as the decision boundary since all points to the left of $L$
belong to $v.lc$ and all points to the right of $L$ belong to $v.rc$. By using
a median point to split the data points, we can ensure that the depth of a
metric-tree is $logn$. Each node $v$ also has a hypersphere $B$, such that all
points represented by $v$ fall in the ball centered at $v.center$ with radius
$v.r$, i.e. $N(v)\in B(v.center,v.r)$.

Searching: A search on a metric-tree is performed using a stack. The current
radius $r$ is used to decide which child node to search first. If the query
$q$ is on the left of current point, then $v.lc$ is searched first, otherwise,
$v.rc$ is searched first. At all times, the algorithm maintains a candidate NN
and there distance determine the current radius, which is the nearest neighbor
it finds so far while traversing the tree. We call this point $x$, and denote
the distance between $q$ and $x$ by $r$. If algorithm is about to exploit a
node $v$, but discovers that no member of $v$ can be within distance $r$ of
$q$, then it skip the subtree from $v$. This happens whenever
$v.center-|q-v.r|\geq r$. In practice, metric tree search typically finds a
very good NN candidate quickly, and then spends lots of the time verifying
that it is in fact the true NN. However, in case of approximate NN we can save
majority of time with moderate approximation guarantee. The algorithm for NN
search using metric tree is given below 1.

###  4.2 Nearest Neighbor search algorithm using M-Tree

algorithm

0: $M=(V,d)$ $\&$ $q$

0: $d(q,v_{q})$

1: Insert root object $v_{r}$ in stack

2: Set current radius as $d(v_{r},q)$

3: Successively traverse the tree in search of $q$

4: PUSH all the objects of traversal path into stack

5: Update the current radius

6: If leaf object reached

7: POP objects from stack

8: For all points lying inside the ball of current radius centering $q$,
verify for possible nearest neighbor and update the current radius.

9: return $d(q,v_{q})$

Algorithm 1 NN search in M-Tree

######  Theorem 4.

Let $M=(V,d)$, be a bounded metric space. Then for any fixed data $V\in R^{n}$
of size $n$, and for constant $c\geq 1$, $\exists\epsilon$ such that we may
compute $d(q,V)|_{\epsilon}$ with at most
$c\cdot\left\lceil\log(n)+1\right\rceil$ expected metric evaluationsCiaccia et
al. (1998)

##  5 Nearest neighbor search on complex network using locality sensitive
hashing

Metric trees, so far represent the practical state of the art for achieving
efficiency in the largest dimensionality possible. However, many real-world
problems are posed with very large dimensionality which are beyond the
capability of such search structures to achieve sub-linear efficiency. Thus,
the high-dimensional case is the long-standing frontier of the nearest-
neighbor problem.

The approximate nearest neighbor can be computed very efficiently using
Locality sensitive hashing.

###  5.1 Approximate nearest neighbor

Given a metric space $(S,d)$ and some finite subset $S_{D}$ of data
points$S_{D}\subset S$ on which nearest neighbor queries are to be made, our
aim to organize $S_{D}$ s.t. NN queries can be answered more efficiently. For
any $q\in S$, NN problem consists of finding single minimal located point
$p\in S_{D}$ s.t. $d(p,q)$ is minimum over all $p\in S_{D}$. We denote this by
$p=NN(q,S_{D})$.

An $\epsilon$ approximate NN of $q\in S$ is to find a point $p\in S_{D}$ s.t.
$d(p,q)\leq(1+\epsilon)d(x,d)$ $\forall$ $x\in S_{D}$.

###  5.2 Locality Sensitive Hashing (LSH)

Several methods to compute first nearest neighbor query exists in the
literatures and locality-sensitive hashing (LSH) is most popular because of
its dimension independent runtime Motwani et al. (2007); Paulevé et al.
(2010). In a locality sensitive hashing, the hash function has the property
that close points are hash into same bucket with high probability and distance
points are hash into same bucket with low probability. Mathematically, a
family $H=\\{h:S\rightarrow U\\}$ is called
$(r_{1},r_{2},p_{1},p_{2})$-sensitive if for any $p,q\in S$

  * •

if $p\in B(q,r_{1})$ then $Pr_{H}[h(q)=h(p)]\geq p_{1}$

  * •

if $p\notin B(q,r_{2})$ then $Pr_{H}[h(q)=h(p)]\leq p_{2}$

where $B(q,r)$ denotes a hypersphere of radius $r$ centered at $q$. In order
for a locality-sensitive family to be useful, it has to satisfy inequalities
$p_{1}>p_{2}$ and $r_{1}<r_{2}$ when $D$ is a dissimilarity measure, or
$p_{1}>p_{2}$ and $r_{1}>r_{2}$ when $D$ is a similarity measureIndyk and
Motwani (1998); Gionis et al. (1999). The value of
$\delta=log(1/P_{1})/log(1/P_{2})$ determines search performance of LSH.
Defining a LSH as $a(r,r(1+\epsilon),p1,p2)$, the $(1+\epsilon)$ NN problem
can be solved via series of hashing and searching within the buckets Joly and
Buisson (2008); Datar et al. (2004); Gionis et al. (1999).

###  5.3 Locality sensitive hash function for complex network

In this sub-section, we discuss the existence of locality sensitive hash
function families for the proposed metric on complex network. The LSH data
structure stores all nodes in hash tables and searches for nearest neighbor
via retrieval. The hash table is contain many buckets and identified by bucket
id. Unlike conventional hashing the LSH approach try to maximize the
probability of collision of near items and put them into same bucket. For any
given the query $q$ the bucket $h(q)$ considered to search nearest node. In
general $k$ hash functions are chosen independently and uniformly at random
from hash family $H$. The output of nearest neighbor query is provided from
the union ok $k$ buckets. The consensus of $k$ functions reduces the error of
approximation. For metric defined in the previous section 3 we considered $k$
random points from the metric space. Each random point $r_{i}$ define a hash
function $h_{i}(x)=sign(d(x,r_{i}))$, where $d$ is the metric and $i\in[1,k]$.
These randomized hash functions are locality sensitive Andoni and Indyk
(2008); Charikar (2002).

0: $M=(V,d)$ $\&$ $q$

0: $d(q,V)$

1: Identify buckets of query point $q$ corresponding to different hash
functions.

2: Compute nearest neighbor of $q$ only for the points inside the selected
buckets.

3: return $d(q,V)$

Algorithm 2 NN search in LSH

######  Theorem 5.

Let $M=(V,d)$, be a bounded metric space. Then for any fixed data $V\in R^{n}$
of size $n$, and for constant $c\geq 1$, $\exists\epsilon$ such that we may
compute $d(q,V)|_{\epsilon}$ with at most $mn^{O(1/\epsilon)}$ expected metric
evaluations, where $m$ is the number of dimension of the metric space. In case
of complex network $m=n$ so expected time is $n^{O(2/\epsilon)}$ Ciaccia et
al. (1998); Indyk (2000).

##  6 Network community detection using nearest neighbor search

Community detection in real networks aims to capture the structural
organization of the network using the connectivity information as inputNewman
and Girvan (2004); Schaeffer (2007). Early work on this domain was attempted
by Weiss and Jacobson while searching for a work group within a government
agencyWeiss and Jacobson (1955).

Most of the methods developed for network community detection are based on a
two-step approach. The first step is specifying a quality measure (evaluation
measure, objective function) that quantifies the desired properties of
communities and the second step is applying an algorithmic techniques to
assign the nodes of graph into communities by optimizing the objective
function.

Several measures for quantifying the quality of communities have been
proposed, they mostly consider that communities are set of nodes with many
edges between them and few connections with nodes of different
communities(e.g. modularity, conductance, expansion, internal density, average
degree, triangle precipitation ratio,..,e.t.c. ).

###  6.1 Popular algorithms

In this subsection we have given a brief list of the algorithms developed for
network community detection purposes. The broad categorization of the
algorithms are based on graph traversal, semidefinite programming and
spectral. The basic approach and the complexity of very popular algorithms are
listed in the table 1. There are more algorithms developed to solve network
community detection problem a complete list can be obtained in several survey
articles Fortunato (2010); Leskovec et al. (2010); Yang and Leskovec (2012).

A partial list of algorithms developed for network community detection purpose
is tabulated in 1. The algorithms are categorized into three main group as
spectral (SP), graph traversal based (GT) and semi-definite programming based
(SDP). The categories and complexities are also given in the table 1.

Table 1: Algorithms for network community detection and their complexities Author | Ref. | Cat. | Order
---|---|---|---
Van Dongen |  (Graph clustering, 2000van Dongen (2000)) | GT |  $O(nk^{2})$, $k<n$ parameter
Eckmann & Moses |  (Curvature, 2002Eckmann and Moses (2002)) | GT | $O(mk^{2})$
Girvan & Newman |  (Modularity, 2002Girvan and Newman (2002)) | SDP | $O(n^{2}m)$
Zhou & Lipowsky |  (Vertex Proximity, 2004Zhou and Lipowsky (2004)) | GT | $O(n^{3})$
Reichardt & Bornholdt |  (spinglass, 2004Reichardt and Bornholdt (2004)) | SDP | parameter dependent
Clauset et al. |  (fast greedy, 2004Clauset et al. (2004)) | SDP | $O(nlog_{2}n)$
Newman & Girvan |  (eigenvector, 2004 Newman and Girvan (2004)) | SP | $O(nm^{2})$
Wu & Huberman |  (linear time, 2004Wu and Huberman (2004)) | GT | $O(n+m)$
Fortunato et al. |  (infocentrality, 2004Fortunato et al. (2004)) | SDP | $O(m^{3}n)$
Radicchi et al. |  (Radicchi et al., 2004Radicchi et al. (2004)) | SP | $O(m^{4}/n^{2})$
Donetti & Munoz |  (Donetti and Munoz, 2004Donetti and Muñoz (2004)) | SDP | $O(n^{3})$
Guimera et al. |  (Simulated Annealing, 2004Guimera and Amaral (2005)) | SDP | parameter dependent
Capocci et al. |  (Capocci et al., 2004Capocci et al. (2004)) | SP | $O(n^{2})$
Latapy & Pons |  (walktrap, 2004Pons and Latapy (2004)) | SP | $O(n^{3})$
Duch & Arenas |  (Extremal Optimization, 2005Duch and Arenas (2005)) | GT | $O(n^{2}logn)$
Bagrow & Bollt |  (Local method, 2005Bagrow and Bollt (2005)) | SDP | $O(n^{3})$
Palla et al. |  (overlapping community, 2005Palla et al. (2005)) | GT | $O(exp(n))$
Raghavan et al. |  (label propagation, 2007Raghavan et al. (2007)) | GT | $O(n+m)$
Rosvall & Bergstrom |  (Infomap, 2008Rosvall and Bergstrom (2008)) | SP | $O(m)$
Ronhovde & Nussinov |  (Multiresolution community, 2009Ronhovde and Nussinov (2009)) | GT |  $O(m\beta logn)$, $\beta\approx 1.3$

###  6.2 k-central algorithm for network community detection using nearest
neighbor search

In this section we have described k-central algorithm for the purpose of
network community detection by using the nearest neighbor search inside
complex network. We have also studied and analyzed the advantages of the
k-central method over the standard algorithm for network community detection.

####  6.2.1 k-central algorithm

The community detection methods based on partitioning of graph is possible
using nearest neighbor search, because the nodes of the graph are converted
into the points of a metric space. This algorithm for network community
detection converges automatically and does not compute the value of objective
function in iterations therefore reduce the computation compared to standard
methods. The results of this algorithm are competitive on a large set networks
shown in section 7. The k-central algorithm for community detection and its
details analysis is given below.

####  6.2.2 k selection

Determining the optimal number of k is an important problem for community
detection researchers. An extensive analysis can be found in the work of
Leskovec et al. Leskovec et al. (2008). The standard practice is to solve an
optimization equation with respect to k for which the optimal value of the
objective function is achieved. Another method based on farthest first
traversal is also very useful in terms of computational efficiency Gonzalez
(1985). For small networks the global optimization works better and for very
large network the second choice give the faster approximate solution.

####  6.2.3 Initialization

The set of initial nodes are also very important problem for k-central
algorithm

  * •

Input: graph $G=(V,E)$, with the node similarity $sim(x_{a},x_{b})$ defined on
it

  * •

Output: A partition of the nodes into $k$ communities $C_{1},C_{2},...,C_{k}$

  * •

Objective function: Maximize the minimum intra community similarity

$min_{j\in\\{1,2,..,k\\}}max_{x_{a},x_{b}\in C_{j}}~{}~{}sim(x_{a},x_{b})$

0: $M=(V,d)$

0: $T=\\{C_{1},C_{2},\dots,C_{k}\\}$ with minimum $cost(T)$

1: Initialize centers $z_{1},\dots,z_{k}\in R^{n}$ and clusters
$T=\\{C_{1},C_{2},\dots,C_{k}\\}$

2: repeat

3: for $i=1$ to $k$ do

4: for $j=1$ to $k$ do

5: $C_{i}\leftarrow\\{x\in V~{}s.t.~{}|z_{i}-x|\leq|z_{j}-x|\\}$

6: end for

7: end for

8: for $j=1$ to $k$ do

9: $z_{i}\leftarrow Central(C_{i})$ ; where $Central(C_{i})$ returns the node
with minimum total distance in the class of consideration.

10: end for

11: until $|cost(T_{t})-cost(T_{t+1})|=0$

12: return $T=\\{C_{1},C_{2},\dots,C_{k}\\}$

Algorithm 3 k-central algorithm

####  6.2.4 Convergence

Convergence of the network community detection algorithms are the least
studied research areas of network science. However, the rate of convergence is
one of the important issues and low rate of convergence is the major pitfall
of the most of the existing algorithms. Due to the transformation into the
metric space, our algorithm equipped with the quick convergence facility of
the k-partitioning on metric space by providing a good set of initial points.
Another crucial pitfall suffer by majority of the existing algorithms is the
validation of the objective function in each iteration during convergence. Our
algorithm converges automatically to the optimal partition thus reduces the
cost of validation during convergence.

######  Theorem 6.

During the course of the $k$ center partitioning algorithm, the cost
monotonically decreases.

###### Proof.

Let $Z^{t}=\\{z_{1}^{t},\dots,z_{k}^{t}\\}$ ,
$T^{t}=\\{C_{1}^{t},\dots,C_{k}^{t}\\}$ denote the centers and clusters at the
start of the $t^{th}$ iteration of $k$ partitioning algorithm. The first step
of the iteration assigns each data point to its closest center; therefore
$cost(T^{t+1},Z^{t})\leq cost(T^{t},Z^{t})$

On the second step, each cluster is re-centered at its mean; therefore
$cost(T^{t+1},Z^{t+1})\leq cost(T^{t+1},Z^{t})$

∎

##  7 Experiments and results

We performed many of experiments to test the performance of nearest neighbor
search based community detection method for complex network over several real
networks2. Objective of the experiment is to verify behavior of the algorithm
and the time required to compute the algorithm. One of the major goals of the
experiment is to verify the behavior of the algorithm with respect to the
performance of other popular methods exists in the literature with respect to
the standard measures like conductance and modularity. Experiments are
conducted to compare the results (tables 3, 4 and 5) of our algorithm with the
state of the art algorithms (table 1) available in the literature in terms of
common measures mostly used by the researchers of the domain of network
community detection. The details of the several experiments and the analysis
of the results are given in the following subsections.

###  7.1 Experimental designs

Experiment for comparison: In this experiment we have compared several
algorithms for network community detection with our proposed algorithm
developed using nearest neighbor search in complex network. Experiment is
performed on a large list of network data sets. Two version of the experiment
is developed for comparison purpose based on two different quality measure
conductance and modularity. The results are shown in the tables 3 and 4
respectively.

Experiment on performance and time: In this experiment we have evaluated our
algorithm for performance on the network collection2. We have evaluated the
time taken by our algorithm on different size of networks and is shown in the
table 5.

###  7.2 Performance indicator

Modularity: The notion of modularity is the most popular for the network
community detection purpose. The modularity index assigns high scores to
communities whose internal edges are more than that expected in a random-
network model which preserves the degree distribution of the given network.

Conductance: Conductance is widely used for graph partitioning literature. The
conductance of a set $S$ with complement $S^{C}$ is the ratio of the number of
edges connecting nodes in $S$ to nodes in $S^{C}$ by the total number of edges
incident to $S$ or to $S^{C}$ (whichever number is smaller).

###  7.3 Datasets

A list of real networks taken from several real life interactions is
considered for our experiments and they are tabulate 2 below. We have also
listed the number of nodes, number of edges, average diameter, data complexity
for community detection (DCC) and the k value used (6.2.2). The values of the
last column can be used to assess the quality of detected communities.

Table 2: Complex network datasets and values of their parameters Name | Type | # Nodes | # Edges | Diameter | k
---|---|---|---|---|---
DBLP | U | 317,080 | 1,049,866 | 8 | 268
Arxiv-AstroPh | U | 18,772 | 396,160 | 5 | 23
web-Stanford | D | 281,903 | 2,312,497 | 9.7 | 69
Facebook | U | 4,039 | 88,234 | 4.7 | 164
Gplus | D | 107,614 | 13,673,453 | 3 | 457
Twitter | D | 81,306 | 1,768,149 | 4.5 | 213
Epinions1 | D | 75,879 | 508,837 | 5 | 128
LiveJournal1 | D | 4,847,571 | 68,993,773 | 6.5 | 117
Orkut | U | 3,072,441 | 117,185,083 | 4.8 | 756
Youtube | U | 1,134,890 | 2,987,624 | 6.5 | 811
Pokec | D | 1,632,803 | 30,622,564 | 5.2 | 246
Slashdot0811 | D | 77,360 | 905,468 | 4.7 | 81
Slashdot0922 | D | 82,168 | 948,464 | 4.7 | 87
Friendster | U | 65,608,366 | 1,806,067,135 | 5.8 | 833
Amazon0601 | D | 403,394 | 3,387,388 | 7.6 | 92
P2P-Gnutella31 | D | 62,586 | 147,892 | 6.5 | 35
RoadNet-CA | U | 1,965,206 | 5,533,214 | 500 | 322
Wiki-Vote | D | 7,115 | 103,689 | 3.8 | 21

###  7.4 Computational results

In this subsection we have compared two groups of algorithms for network
community detection with our proposed algorithm using nearest neighbor search.
Experiment is performed on a large list of network data sets. Two version of
the experiment is developed for comparison purpose based on two different
quality measure conductance and modularity. The results based on conductance
is shown in the table 3 and the results based on modularity is shown in the
table 4, respectively. Regarding the two groups of algorithms; first group
contain algorithms based on semi-definite programming and the second group
contain algorithms based on graph traversal approaches. For each group, we
have taken the best value of conductance in table 3 and best value of
modularity in table 4 among all the algorithms in the groups. The results
obtained with our approach are very competitive with most of the well known
algorithms in the literature and this is justified over the large collection
of datasets. On the other hand, it can be observed that time taken (table 5)
by our algorithm is quite less compared to other methods and justify the
theoretical findings.

Table 3: Comparison of our approaches with other best methods in terms of conductance Name | Spectral | SDP | GT | Index | M-tree | LSH
---|---|---|---|---|---|---
Facebook | 0.0097 | 0.1074 | 0.1044 | 0.1082 | 0.0827 | 0.0340
Gplus | 0.0119 | 0.1593 | 0.1544 | 0.1602 | 0.1207 | 0.0500
Twitter | 0.0035 | 0.0480 | 0.0465 | 0.0483 | 0.0363 | 0.0150
Epinions1 | 0.0087 | 0.1247 | 0.1208 | 0.1254 | 0.0941 | 0.0390
LiveJournal1 | 0.0039 | 0.0703 | 0.0680 | 0.0706 | 0.0523 | 0.0218
Pokec | 0.0009 | 0.0174 | 0.0168 | 0.0175 | 0.0129 | 0.0054
Slashdot0811 | 0.0005 | 0.0097 | 0.0094 | 0.0098 | 0.0072 | 0.0030
Slashdot0922 | 0.0007 | 0.0138 | 0.0133 | 0.0138 | 0.0102 | 0.0043
Friendster | 0.0012 | 0.0273 | 0.0263 | 0.0273 | 0.0200 | 0.0084
Orkut | 0.0016 | 0.0411 | 0.0397 | 0.0412 | 0.0300 | 0.0126
Youtube | 0.0031 | 0.0869 | 0.0838 | 0.0871 | 0.0633 | 0.0267
DBLP | 0.0007 | 0.0210 | 0.0203 | 0.0211 | 0.0152 | 0.0064
Arxiv-AstroPh | 0.0024 | 0.0929 | 0.0895 | 0.0931 | 0.0669 | 0.0283
web-Stanford | 0.0007 | 0.0320 | 0.0308 | 0.0320 | 0.0229 | 0.0097
Amazon0601 | 0.0018 | 0.0899 | 0.0865 | 0.0900 | 0.0643 | 0.0273
P2P-Gnutella31 | 0.0009 | 0.0522 | 0.0503 | 0.0523 | 0.0373 | 0.0158
RoadNet-CA | 0.0024 | 0.1502 | 0.1445 | 0.1504 | 0.1070 | 0.0455
Wiki-Vote | 0.0026 | 0.1853 | 0.1783 | 0.1855 | 0.1318 | 0.0561
Table 4: Comparison of our approaches with other best methods in terms of modularity Name | Spectral | SDP | GT | Index | M-tree | LSH
---|---|---|---|---|---|---
Facebook | 0.4487 | 0.5464 | 0.5434 | 0.5472 | 0.5450 | 0.5421
Gplus | 0.2573 | 0.4047 | 0.3998 | 0.4056 | 0.4041 | 0.4021
Twitter | 0.3261 | 0.3706 | 0.3691 | 0.3709 | 0.3692 | 0.3669
Epinions1 | 0.0280 | 0.1440 | 0.1401 | 0.1447 | 0.1443 | 0.1437
LiveJournal1 | 0.0791 | 0.1455 | 0.1432 | 0.1458 | 0.1450 | 0.1439
Pokec | 0.0129 | 0.0294 | 0.0288 | 0.0295 | 0.0292 | 0.0287
Slashdot0811 | 0.0038 | 0.0130 | 0.0127 | 0.0131 | 0.0129 | 0.0127
Slashdot0922 | 0.0045 | 0.0176 | 0.0171 | 0.0176 | 0.0174 | 0.0172
Friendster | 0.0275 | 0.0536 | 0.0526 | 0.0536 | 0.0531 | 0.0525
Orkut | 0.0294 | 0.0689 | 0.0675 | 0.0690 | 0.0685 | 0.0678
Youtube | 0.0096 | 0.0934 | 0.0903 | 0.0936 | 0.0934 | 0.0930
DBLP | 0.4011 | 0.4214 | 0.4207 | 0.4215 | 0.4196 | 0.4171
Arxiv-AstroPh | 0.4174 | 0.5079 | 0.5045 | 0.5081 | 0.5061 | 0.5035
web-Stanford | 0.3595 | 0.3908 | 0.3896 | 0.3908 | 0.3890 | 0.3866
Amazon0601 | 0.1768 | 0.2649 | 0.2615 | 0.2650 | 0.2637 | 0.2621
P2P-Gnutella31 | 0.0009 | 0.0522 | 0.0503 | 0.0523 | 0.0523 | 0.0523
RoadNet-CA | 0.0212 | 0.1690 | 0.1633 | 0.1692 | 0.1680 | 0.1664
Wiki-Vote | 0.0266 | 0.2093 | 0.2023 | 0.2095 | 0.2090 | 0.2083
Table 5: Comparison of our approaches with other best methods in terms of time Name | Spectral | SDP | GT | Index | M-tree | LSH
---|---|---|---|---|---|---
Facebook | 6 | 7 | 11 | 6 | 4 | 1
Gplus | 797 | 832 | 1342 | 661 | 390 | 115
Twitter | 462 | 485 | 786 | 398 | 235 | 68
Epinions1 | 411 | 419 | 667 | 292 | 174 | 56
LiveJournal1 | 1297 | 1332 | 2129 | 969 | 576 | 179
Pokec | 1281 | 1305 | 2075 | 901 | 538 | 173
Slashdot0811 | 552 | 561 | 891 | 382 | 228 | 74
Slashdot0922 | 561 | 570 | 906 | 389 | 232 | 75
Friendster | 2061 | 2105 | 3352 | 1477 | 880 | 280
Orkut | 1497 | 1529 | 2435 | 1074 | 640 | 203
Youtube | 829 | 844 | 1340 | 578 | 345 | 111
DBLP | 381 | 403 | 655 | 341 | 201 | 57
Arxiv-AstroPh | 217 | 230 | 375 | 197 | 116 | 33
web-Stanford | 498 | 525 | 852 | 437 | 258 | 74
Amazon0601 | 653 | 678 | 1089 | 520 | 308 | 93
P2P-Gnutella31 | 182 | 184 | 293 | 124 | 74 | 24
RoadNet-CA | 758 | 785 | 1261 | 599 | 355 | 107
Wiki-Vote | 54 | 55 | 88 | 39 | 23 | 7

###  7.5 Results analysis and achievements

In this subsection, we have described the analysis of the results obtained in
our experiments shown above and also highlighted the achievements from the
results. It is clearly evident from the results shown in the tables 3, 4 and 5
that, proposed nearest neighbor based method for network community detection
using metric tree and locality sensitive hashing provide very good competitive
performance with respect to conductance and modularity and also in terms of
time. It is also evident from the results that our methods provide case base
solution of network community detection depending on the requirements of time
or better conductance/modularity.

##  8 Conclusions

In this paper, we have studied the interesting problem of nearest neighbor
queries in complex networks. Processing nearest neighbor search in complex
networks cannot be achieved by straightforward applications of previous
approaches for the Euclidean space due to the complexity of graph traversal
based computations of node nearness as opposed to geometric distances. We
presented the transformation of graph to metric space and efficient
computation of nearest neighbor therein using metric tree and locality
sensitive hashing. Our techniques can be applied for various structural
analysis of complex network using geometric approaches. To validate the
performance of proposed nearest neighbor search designed for complex networks
we applied our approaches on community detection problem. The results obtained
on several network data sets prove the usefulness of the proposed method and
provide motivation for further application of other structural analysis of
complex network using nearest neighbor search.

###### Acknowledgements.

Acknowledgments This work is supported by the Jaypee University of Information
Technology. Author Contributions Suman Saha proposed the algorithm and
prepared the manuscript. S.P. Ghrera was in charge of the overall research and
critical revision of the paper. Conflicts of Interest The authors declare no
conflict of interest.

## References

  * Uhlmann (1991) Uhlmann, J.K.  Satisfying general proximity / similarity queries with metric trees.  Information Processing Letters 1991, 40, 175 – 179\.
  * Ruiz (1986) Ruiz, E.V.  An algorithm for finding nearest neighbours in (approximately) constant average time.  Pattern Recognition Letters 1986, 4, 145 – 157.
  * Panigrahy (2006) Panigrahy, R.  Entropy Based Nearest Neighbor Search in High Dimensions.  Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 2006; SODA ’06, pp. 1186–1195.
  * Indyk and Motwani (1998) Indyk, P.; Motwani, R.  Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.  Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing; ACM: New York, NY, USA, 1998; STOC ’98, pp. 604–613.
  * Gionis et al. (1999) Gionis, A.; Indyk, P.; Motwani, R.  Similarity Search in High Dimensions via Hashing.  Proceedings of the 25th International Conference on Very Large Data Bases; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 1999; VLDB ’99, pp. 518–529.
  * Dasgupta and Freund (2008) Dasgupta, S.; Freund, Y.  Random Projection Trees and Low Dimensional Manifolds.  Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing; ACM: New York, NY, USA, 2008; STOC ’08, pp. 537–546.
  * Akoglu et al. (2014) Akoglu, L.; Khandekar, R.; Kumar, V.; Parthasarathy, S.; Rajan, D.; Wu, K.L.  Fast Nearest Neighbor Search on Large Time-Evolving Graphs.  Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases - Volume 8724; Springer-Verlag New York, Inc.: New York, NY, USA, 2014; ECML PKDD 2014, pp. 17–33.
  * Liu et al. (2004) Liu, T.; Moore, A.W.; Gray, E.; Yang, K.  An investigation of practical approximate nearest neighbor algorithms.  NIPS2004. MIT Press, 2004, pp. 825–832.
  * Freeman (1978) Freeman, L.C.  Centrality in social networks conceptual clarification.  Social Networks 1978, p. 215.
  * Carrington et al. (2005) Carrington, P.J.; Scott, J.; Wasserman, S., Eds.  Models and methods in social network analysis; Cambridge University Press, 2005.
  * Newman (2003) Newman, M.  The Structure and Function of Complex Networks.  SIAM review 2003, 45, 167–256.
  * Radicchi et al. (2004) Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; Parisi, D.  Defining and identifying communities in networks.  Proceedings of the National Academy of Sciences 2004, 101, 2658.
  * Fortunato (2010) Fortunato, S.  Community detection in graphs.  Physics Reports 2010, 486, 75 – 174.
  * Weiss and Jacobson (1955) Weiss, R.; Jacobson, E.  A Method for the Analysis of Complex Organisations.  American Sociological Review 1955, 20, 661–668.
  * Schaeffer (2007) Schaeffer, S.E.  Graph clustering.  Computer Science Review 2007, 1, 27 – 64.
  * Newman and Girvan (2004) Newman, M.E.J.; Girvan, M.  Finding and evaluating community structure in networks.  Physical Review 2004, E 69.
  * Luxburg (2007) Luxburg, U.  A tutorial on spectral clustering.  Statistics and Computing 2007, 17, 395–416.
  * Pons and Latapy (2004) Pons, P.; Latapy, M.  Computing communities in large networks using random walks.  J. of Graph Alg. and App. 2004, 10, 284–293.
  * Duch and Arenas (2005) Duch, J.; Arenas, A.  Community detection in complex networks using Extremal Optimization.  Physical Review E 2005, 72, 027104.
  * Chakrabarti (2004) Chakrabarti, D.  AutoPart: Parameter-Free Graph Partitioning and Outlier Detection.  PKDD; Boulicaut, J.F.; Esposito, F.; Giannotti, F.; Pedreschi, D., Eds. Springer, 2004, Vol. 3202, Lecture Notes in Computer Science, pp. 112–124.
  * Macropol and Singh (2010) Macropol, K.; Singh, A.K.  Scalable Discovery of Best Clusters on Large Graphs.  PVLDB 2010, 3, 693–702.
  * Levorato and Petermann (2011) Levorato, V.; Petermann, C.  Detection of communities in directed networks based on strongly p-connected components.  CASoN. IEEE, 2011, pp. 211–216.
  * Brandes et al. (2003) Brandes, U.; Gaertler, M.; Wagner, D.  Experiments on Graph Clustering Algorithms.  ESA; Battista, G.D.; Zwick, U., Eds. Springer, 2003, Vol. 2832, Lecture Notes in Computer Science, pp. 568–579.
  * Bullmore and Sporns (2009) Bullmore, E.; Sporns, O.  Complex brain networks: graph theoretical analysis of structural and functional systems.  Nature Reviews Neuroscience 2009, 10, 186–198.
  * Saha and Ghrera (2015) Saha, S.; Ghrera, S.P.  Network Community Detection on Metric Space.  Algorithms 2015, 8, 680–696.
  * Ciaccia et al. (1997) Ciaccia, P.; Patella, M.; Zezula, P.  M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.  Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB’97); Morgan Kaufmann Publishers, Inc.: Athens, Greece, 1997; pp. 426–435.
  * Ciaccia et al. (1998) Ciaccia, P.; Patella, M.; Zezula, P.  A Cost Model for Similarity Queries in Metric Spaces.  Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’97); ACM Press: Seattle, WA, 1998; pp. 59–68.
  * Motwani et al. (2007) Motwani, R.; Naor, A.; Panigrahy, R.  Lower Bounds on Locality Sensitive Hashing.  SIAM J. Discrete Math. 2007, 21, 930–935.
  * Paulevé et al. (2010) Paulevé, L.; Jégou, H.; Amsaleg, L.  Locality Sensitive Hashing: A Comparison of Hash Function Types and Querying Mechanisms.  Pattern Recogn. Lett. 2010, 31, 1348–1358.
  * Indyk and Motwani (1998) Indyk, P.; Motwani, R.  Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.  Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing; ACM: New York, NY, USA, 1998; STOC ’98, pp. 604–613.
  * Gionis et al. (1999) Gionis, A.; Indyk, P.; Motwani, R.  Similarity Search in High Dimensions via Hashing.  Proceedings of the 25th International Conference on Very Large Data Bases; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 1999; VLDB ’99, pp. 518–529.
  * Joly and Buisson (2008) Joly, A.; Buisson, O.  A posteriori multi-probe locality sensitive hashing.  ACM Multimedia; El-Saddik, A.; Vuong, S.; Griwodz, C.; Bimbo, A.D.; Candan, K.S.; Jaimes, A., Eds. ACM, 2008, pp. 209–218.
  * Datar et al. (2004) Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V.S.  Locality-sensitive Hashing Scheme Based on P-stable Distributions.  Proceedings of the Twentieth Annual Symposium on Computational Geometry; ACM: New York, NY, USA, 2004; SCG ’04, pp. 253–262.
  * Andoni and Indyk (2008) Andoni, A.; Indyk, P.  Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions.  Commun. ACM 2008, 51, 117–122.
  * Charikar (2002) Charikar, M.S.  Similarity Estimation Techniques from Rounding Algorithms.  Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing; ACM: New York, NY, USA, 2002; STOC ’02, pp. 380–388.
  * Indyk (2000) Indyk, P.  A Sublinear Time Approximation Scheme for Clustering in Metric Spaces.  Proc. 40th IEEE FOCS, 2000, pp. 154–159.
  * Leskovec et al. (2010) Leskovec, J.; Lang, K.J.; Mahoney, M.W.  Empirical comparison of algorithms for network community detection.  WWW; Rappa, M.; Jones, P.; Freire, J.; Chakrabarti, S., Eds. ACM, 2010, pp. 631–640.
  * Yang and Leskovec (2012) Yang, J.; Leskovec, J.  Defining and Evaluating Network Communities Based on Ground-Truth.  ICDM; Zaki, M.J.; Siebes, A.; Yu, J.X.; Goethals, B.; Webb, G.I.; Wu, X., Eds. IEEE Computer Society, 2012, pp. 745–754.
  * van Dongen (2000) van Dongen, S.  A Cluster Algorithm For Graphs.  Technical Report INS-R 0010, CWI, Amsterdam, the Netherlands, 2000.
  * Eckmann and Moses (2002) Eckmann, J.P.; Moses, E.  Curvature of co-links uncovers hidden thematic layers in the World Wide Web.  PNAS 2002, 99, 5825–5829.
  * Girvan and Newman (2002) Girvan, M.; Newman, M.E.J.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences 2002, 99, 7821–7826.
  * Zhou and Lipowsky (2004) Zhou, H.; Lipowsky, R.  Network Brownian Motion: A New Method to Measure Vertex-Vertex Proximity and to Identify Communities and Subcommunities.  International Conference on Computational Science; Bubak, M.; van Albada, G.D.; Sloot, P.M.A.; Dongarra, J., Eds. Springer, 2004, Vol. 3038, Lecture Notes in Computer Science, pp. 1062–1069.
  * Reichardt and Bornholdt (2004) Reichardt, J.; Bornholdt, S.  Detecting fuzzy community structures in complex networks with a Potts model.  Phys Rev Lett 2004, 93, 218701.
  * Clauset et al. (2004) Clauset, A.; Newman, M.E.J.; .; Moore, C.  Finding community structure in very large networks.  Physical Review E 2004, pp. 1– 6.
  * Wu and Huberman (2004) Wu, F.; Huberman, B.  Finding communities in linear time: a physics approach.  The European Physical Journal B - Condensed Matter and Complex Systems 2004, 38, 331–338.
  * Fortunato et al. (2004) Fortunato, S.; Latora, V.; Marchiori, M.  Method to find community structures based on information centrality.  Physical Review E (Statistical, Nonlinear, and Soft Matter Physics) 2004, 70, 056104.
  * Donetti and Muñoz (2004) Donetti, L.; Muñoz, M.A.  Detecting network communities: a new systematic and efficient algorithm.  Journal of Statistical Mechanics: Theory and Experiment 2004, 2004, P10012.
  * Guimera and Amaral (2005) Guimera, R.; Amaral, L.A.N.  Functional cartography of complex metabolic networks.  Nature 2005, 433, 895–900.
  * Capocci et al. (2004) Capocci, A.; Servedio, V.D.P.; Caldarelli, G.; Colaiori, F.  Detecting communities in large networks.  Physica A: Statistical Mechanics and its Applications 2004, 352, 669–676.
  * Duch and Arenas (2005) Duch, J.; Arenas, A.  Community detection in complex networks using Extremal Optimization.  Physical Review E 2005, 72, 027104.
  * Bagrow and Bollt (2005) Bagrow, J.P.; Bollt, E.M.  Local method for detecting communities.  Phys. Rev. E 2005, 72, 046108.
  * Palla et al. (2005) Palla, G.; Derenyi, I.; Farkas, I.; Vicsek, T.  Uncovering the overlapping community structure of complex networks in nature and society.  Nature 2005, 435, 814–818.
  * Raghavan et al. (2007) Raghavan, U.N.; Albert, R.; Kumara, S.  Near linear time algorithm to detect community structures in large-scale networks.  Phys. Rev. E 2007, 76, 036106.
  * Rosvall and Bergstrom (2008) Rosvall, M.; Bergstrom, C.T.  Maps of random walks on complex networks reveal community structure.  Proceedings of the National Academy of Sciences 2008, 105, 1118–1123.
  * Ronhovde and Nussinov (2009) Ronhovde, P.; Nussinov, Z.  Multiresolution community detection for megascale networks by information-based replica correlations.  Phys. Rev. E 2009, 80, 016109.
  * Leskovec et al. (2008) Leskovec, J.; Lang, K.J.; Dasgupta, A.; Mahoney, M.W.  Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters, 2008.
  * Gonzalez (1985) Gonzalez, T.F.  Clustering to Minimize the Maximum Intercluster Distance.  Theor. Comput. Sci. 1985, 38, 293–306.