Task:
Given a graph \(G=(V,E)\) , we denote the degree of a node
\(u\)  by \(\delta _u\) . If we consider a subset of nodes \(V^{\prime }\subseteq V\)  that are densely connected and represent a
community, to which node \(u\)  belongs. We denote the
sum of degrees of the nodes present in \(V^{\prime }\)  by
\(\delta _u(V)\) . Then, this total degree can be split into two
contributions
\(\delta _u(V) = \delta _u^{in}(V^{\prime }) + \delta _u^{out}(V^{\prime })\) 
where \(\delta _u^{in}(V^{\prime })\)  is the number of edges connecting
\(u\)  to other nodes in \(V^{\prime }\)  and
\(\delta _u^{out}(V^{\prime })\)  is the number of edges connecting \(u\) 
to \(V \setminus V^{\prime }\)  (i.e., rest of the nodes outside
\(V^{\prime }\) ). The subset \(V^{\prime }\)  is a termed a community in the
strong sense, if
\(\delta _u^{in}(V^{\prime }) > \delta _u^{out}(V^{\prime }) \text{,\hspace{20.0pt}} \forall u \in V^{\prime }\) 
Dataset:
We downloaded the Facebook graph
datasethttp://snap.stanford.edu/data/ego-Facebook.html
from SNAP [1]}.
This dataset consists of circles (or friends
lists) from Facebook. Facebook data was collected from survey
participants using this Facebook application. We used a
smaller subset of the large graph, by taking into account
2094 vertices and 20K edges connecting them.
Experimental Setup:
As this was an undirected graph dataset, we
assigned an orientation to each edge \((u,v)\) , by setting \(u \over \longrightarrow  v\) , if \(u < v\) , and \(u  \over \longleftarrow  v\) , if \(u >v\) . Accordingly, an edge weight was also assigned as
\(|u-v|\) . \(H\)  was fixed at 3, in our experiments. We first
computed a node embedding as was done in
Section REF , ran a DBSCAN density-based
clustering, and mapped the clusters back to the original
nodes in the graph.
Results:
We detected 7 different communities that are each
uniquely colored and depicted in
Figure REF (b). It can be visually observed that
our method does a fairly good job of detecting communities
in the strong sense in the Facebook graph.

