Community detection using boundary nodes in complex networks
Mursel Tasgin Haluk O. Bingol
 







	Department of Computer Engineering

	Bogazici University, Istanbul







We propose a new local community detection algorithm 
that finds communities by identifying borderlines between them using boundary nodes. 
Our method performs label propagation
for community detection,
where nodes decide
their labels based on the largest “benefit score” 
exhibited by their immediate neighbors as an attractor to their communities.
We try different metrics and find that 
using the number of common neighbors as benefit scores
leads to better decisions for 
community structure. 
The proposed algorithm has a local approach 
and focuses only on boundary nodes
during iterations of label propagation,
which eliminates 
unnecessary steps and
shortens the overall execution time.
It preserves small communities
as well as big ones and can outperform other algorithms in terms of 
the quality of the identified communities,
especially when the community structure is subtle.
The algorithm has a distributed nature 
and can be used on large networks in a parallel fashion. 


89.75.Hc, 89.65.Ef, 89.75.Fb

	Community detection using boundary nodes in complex networks

    Haluk O. Bingol
    December 30, 2023
===============================================================










§ INTRODUCTION



A system consisting of elements can be expressed
by using network representation,
i.e.,
nodes denote the elements and 
edges represent their relations. 
Many real-life systems,
e.g., 
mobile communication networks, 
collaboration networks,
protein-protein interaction networks are analyzed using 
network representation <cit.>.
A community is defined as a group of nodes in a network 
where nodes within the same group have more connections with 
each other than 
the nodes from other groups <cit.>. 
Community detection is the task of identifying such groups in a network.
Although there is not a universally accepted definition of a community,
the above definition is used by many community detection algorithms <cit.>.
There is a comprehensive survey on community detection methods 
and algorithms in complex networks
by Fortunato <cit.>.
Different aspects and purposes of community detection 
are investigated in a recent 
work by Schaub et al.<cit.>.
Authors discuss that understanding the motivation of community detection 
for a specific problem is important for 
selecting the most suitable algorithm or approach,
since there are many facets of community detection.

Many of the proposed community detection algorithms, 
some of which are nearly a decade old or more, 
are successful on small networks of hundreds or thousands of nodes.
With the availability of very large network datasets 
having millions or billions of nodes and edges
in recent years,
there are challenges for community detection algorithms.
Many of the existing community detection algorithms are not able to
run on such large networks
because of their high time-complexity.
If a community detection algorithm needs to optimize a global value or 
a metric regarding the whole network,
then it may need to perform an operation or 
calculation related 
with all elements of the network (i.e. nodes and edges) many times.
Such an approach is computationally expensive and is not feasible
on very large networks.
Additionally,
processing the whole network data may require storing 
and accessing it many times, which is expensive in 
terms of data storage, too.
A local community detection approach,
which uses local information around a node while identifying its community,
can be a practical solution on very large networks.
When the community of each node is decided 
using such a limited data and 
calculation, 
then overall time-complexity of the algorithm will be reasonably low
on very large networks.
Besides their practicality, local algorithms may be 
the only viable options 
on these networks.

In this paper, we propose a new community detection algorithm 
that has a local approach 
and tries to find communities by identifying borderlines between them 
using boundary nodes.
Initially,
every node is considered to be a boundary node.
Our community detection process naturally 
decreases their numbers by identifying communities of them.
In the final situation,
only the actual boundary nodes remain
and they constitute the borderlines between communities.

Outline of the paper is as follows.
We first give background information about our notation,
local algorithms and our method of testing.
Then we briefly explain our community detection approach.
We go into the details of experiments and 
present the results of our algorithm on 
both generated and real-life networks
and compare it with other algorithms.





§ BACKGROUND






 §.§ Notation



Let G = (V, E) be an unweighted and undirected graph 
where 
V is the set of nodes and 
E is the set of edges.
A community structure is a partition of V.
We label each block in the partition 
using a symbol in the set of community labels
= { 1, …, V}.
We define function
L  V →, 
which maps each node in V to a community label in .
That is, 
the community of node i ∈ V is given as L(i).
If two nodes i and j are in the same community,
then we have L(i) = L(j).

In community detection,
triangles,
i.e.,
three nodes connected by three edges,
play an important role <cit.>.
We use two metrics related to triangles.
First one, the clustering coefficient CC_i of node i, is 
the probability that two of its neighbors are friends of each other,
given as

    CC_i= △_i/∧_i

where 
△_i is the number of triangles around node i and 
∧_i is the number of triplets, 
i.e.,
i is connected to two nodes,
centered at 
i <cit.>.
The second metric is the number of common neighbors of two nodes, 
which is generally used for node similarity.
The number of common neighbors of nodes i and j is given as

    ij = Γ(i) ∩Γ(j)

where
Γ(i) is the 1-neighborhood of i,
i.e.,
the set of nodes whose distances to i are 1.

We use the concepts of  <cit.> 
to mark the nodes.
A node i is called an interior node 
if it is in the same community with all of its 1-neighbors. 
If it is not an interior node, it is called a boundary node.
Note that boundary nodes are positioned 
among nodes from different communities.







 §.§ Local community detection algorithms



In recent years, several local community detection 
algorithms have been proposed <cit.>.
These algorithms generally discover 
communities using local interactions of nodes 
or local metrics calculated in the 1-neighborhood of nodes in the network.
Instead of performing a search or a 
calculation on the whole network (i.e. global), 
local approach splits the community detection task 
into separate subtasks
on individual nodes and their neighborhoods.
Results of these subtasks are then
merged together to get the 
community structure of the whole network.

Raghavan et al. <cit.> 
proposed label propagation algorithm,
denoted by LPA, 
which updates the community label of each node with
the most popular label in its 1-neighborhood,
i.e., 
majority rule of labels.
Labels of all nodes in the network are updated asynchronously and 
algorithm terminates 
when there is no possible label update in the network.
It is a linear-time algorithm, 
which can identify communities in a fast way.
However,
it tends to find a single large community,
especially when community structure is subtle.

 <cit.> 
proposed an extension on LPA, 
which we denote by , 
using neighborhood-strength driven approach.
 improves the quality of identified communities
by incorporating the number of common neighbors
to the majority rule of labels in LPA.
It calculates the scores of labels by 
first counting the number of members 
having these labels, 
which is similar to LPA.
Then it adds the number of common 
neighbors each group has with the node,
multiplied with a constant, c < 1.

Additionally,
LPAc also decreases the number of execution steps by 
avoiding unnecessary label updates.
Only a subset of nodes in the network update their labels,
namely, active boundary nodes.
Algorithm defines a node as passive if it
would not change its label when there is 
an attempt to update it;
a node that is not passive is called active.
It keeps a list of both types and
iteratively selects a node i from the 
active boundary list and updates its label, L(i).
After the label update, 
status of node i is checked and 
if it becomes a passive or an interior node,
it is removed from active boundary list.

After label update, neighbors of i are checked for a change of status,
i.e.,
if they become active boundary nodes,
they are inserted into the list;
if they change from active to passive, 
they are removed from the list.
The algorithm iteratively identifies 
the labels of nodes in active boundary list and
maintains the list with removals and 
insertions of nodes with label updates.
Algorithm completes when the active boundary list is empty.
Despite the increased quality of communities and its speed,
LPAc still has the issue of finding a single 
community, which is a drawback of LPA, too.






 §.§ Method for testing of algorithms


A community detection algorithm outputs a partition of the set of vertices,
where each block of the partition corresponds to a community.
When we have the ground-truth community structure of the network,
we can compare the partition output of 
the algorithm with that of the ground-truth
using Normalized Mutual Information (NMI) <cit.>.

We start testing our algorithm on real-life 
networks with ground-truth community structure.
The first network is the small network of Zachary karate club <cit.>.
Then, we use larger networks provided by 
SNAP <cit.>, 
namely;
DBLP network, 
Amazon co-purchase network, YouTube network and 
European-email network,
which all have ground-truth communities.
Although we use the provided
ground-truth communities,
which are created by using some meta-data related to these networks,
Peel et al. <cit.>
present a detailed analysis on whether the given meta-data can 
explain the actual ground-truth communities for the corresponding network.
When an algorithm finds the communities
on a network that are different from the communities
explained by meta-data, 
then it may not be directly related with algorithm's failure;
but there may be other reasons, 
i.e. 
irrelevant meta-data, 
meta-data showing different aspects of the network or 
no community structure in the network.


On real-life networks, 
we run some of the known community detection algorithms;
namely 
Newman's fast greedy algorithm 
(NM) <cit.>, 
Infomap 
(Inf) <cit.>, 
Louvain 
(Lvn) <cit.>,
LPA <cit.>,
and
LPAc <cit.> 
and compare their results with the ground-truth. 
Execution times of the algorithms are also measured and reported.
Experiments are done with a computer 
having 2.2 GHz Intel Core i7 processor with 4-cores.

We also use a set of computer generated networks for testing.
The LFR benchmark networks <cit.>, 
with planted community structure, 
are used for comparison of community detection algorithms.
These networks are generated with a parameter vector of 
[N, ⟨ k⟩, k_max, C_min, C_max, μ]
where 
N is the number of nodes and 
μ is the mixing parameter controlling the rate of 
intra-community edges to all edges of nodes in the generated network.
Community structure of an LFR network is 
related to the mixing parameter it is generated with.
As μ increases, 
the community structure becomes more subtle and difficult to identify.
LFR algorithm runs in a non-deterministic way and 
can create different networks, 
given the same parameter vector.
In order to avoid a potential bias of an algorithm to a single network,
we generate 100 LFR networks for each vector and report the averages.







§ OUR APPROACH


We propose a new community detection algorithm that finds communities
by identifying borderlines between communities based on boundary nodes.
We first provide an overview of the algorithm,
then we discuss the details.
The algorithm Community-By-BoundryNodes 
is given in fig:Community-By-BoundryNodes.











The algorithm keeps track of a set S of boundary nodes.
We start with |V| communities of size 1,
i.e., 
each node is a community by itself.
Since each node is a boundary node,
the set initially 
would have all the nodes in it.

Set S with |V|-elements is too large.
We apply a heuristic, 
Initial-Heuristic in fig:Initial-Heuristic,
to reduce the initial number of communities, 
hence, 
the initial number of boundary nodes.
For each connected pair of nodes i,j∈ V,
we calculate the “benefit score”, 
,
if i assumes the community of j ∈Γ(i).
Note that  is calculated synchronously.

We set the community of i to that of j with the maximum benefit score.
Then, 
using procedure isBoundryNode in fig:isBoundryNode,
we identify the boundary nodes and insert them into the set S.





















 


As long as the set is not empty,
the algorithm repeats the following steps.
A node i in the set is selected at random 
and removed from the set.
	We reconsider the community of the selected node based on its 1-neighborhood.
	A new community assignment, 
	which produces the largest “benefit score”, 
	is made.

If the old and the new communities of i are the same,
i.e. no effective change,
then we are done with this pass.
If the community of i is changed,
then this may cause some of its 1-neighbors

to become boundary nodes.
In this case, 
the new boundary nodes are inserted into the set.
Note that the selected node is not added to the set during this iteration
even if it is still a boundary node.
It is possible that it may be inserted into the set in some other iteration,
in which one of its 1-neighbors is processed.
Boundary node check is done with procedure isBoundryNode.





This iteration process terminates 
when the set S becomes empty,
which indicates that the system reaches to a steady state,
where no further change in community assignment is possible
with a larger “benefit score”.
 





 §.§ Best Community


Given a community assignment,
we want to reconsider the community L(i) of a node i by 
investigating options in its 1-neighborhood Γ(i).
This is the function of the procedure 
bestCommunity,
which is described below.

There are two different approaches:


a) Individual approach.
Consider each neighbor j ∈Γ(i) of i individually.
Switching to the community of j produces a benefit of .
Therefore, 
i switches to the community of j, 
which produces the largest benefit.
That is,

    L(i) 
    	= L(
    		j ∈Γ(i)).

If there is more than one community with the maximum benefit,
one of them is selected randomly.



For the value of ,
we consider three metrics:

(i) :
Assign a uniformly random number in a range of [0, 1] to .
Clearly,
this will not reflect any information regarding the properties of a node or its neighborhood.

(ii) :
Use the clustering coefficient of j as the benefit score,
i.e.,
= CC_j.

(iii) :
Use the number of common neighbors of i and j,
i.e., 
= ij.




b) Community groups approach.
We consider the communities represented by the neighbors. 
The neighbors are grouped according to their communities.
We look at the collective contribution of each group.
The community of the group with the largest benefit score 
is selected as the new community of i.
That is,

    L(i) 
    	= L(
    		k 
    			B_i(k)
    	)

where 
B_i(k) is the collective benefit score of 
community k 
in 1-neighborhood of node i
and defined as

    B_i(k) 
    	= ∑_
    				L(j) = k
    
    				j ∈Γ(i)
    			.





For the value of ,
we consider the three metrics
that we used in the individual approach.
The group versions are denoted by

(iv): ,

(v): , and

(vi): .

In addition to these,
we consider one more measure:

(vii): :
We assign = 1 to each neighbor j.
Note that this is similar to the majority rule of labels in LPA.

 




§ EXPERIMENTS AND DISCUSSION









 §.§ Deciding the benefit score


We define seven metrics for benefit score.
In order to decide on which metric to use, 
we try each one on LFR generated networks of 1,000 nodes.


NMI scores of identified partitions and execution times of our algorithm are presented 
in fig:LFR1000_benefitScores 
and fig:LFR1000_benefitScoreExecutionTimes, 
respectively.
We also run LPA and algorithms on these networks for comparison.
The c parameter of  is set as 0.25.






 





 
We observe that all the group-based benefit scores have 
better results than the individual ones. 
Even group-random value assignment, , has good results.


Surprisingly, 
uniform benefit score using the group approach, ,
has the worst performance among all.
Although it is similar to the majority rule of labels in the LPA, 
it is not a good fit for our algorithm.
As an exception among the individual ones,
 outperforms LPA.


Benefit scores based on common neighbors,
both at individual and group level,
i.e.,
 and ,
produce better results in our tests.
 is slightly better than  in terms of NMI values.

Both LPA and  algorithms have good NMI values, 
but when μ > 0.6, 
their performances degrade while our algorithm still finds communities.
 performs better than LPA.
However, when we look at the execution times of algorithms, 
 has the worst performance.
Its elapsed time is 2 to 3 times higher than our  algorithm.


We conclude that using the number of common neighbors with
the community-groups approach, namely ,
produces the best results in our algorithm.
We use  for the rest of the paper.





 §.§ Zachary karate club network







 





We run our algorithm on Zachary karate club network and 
compare the identified communities with the ground-truth.
Our algorithm identifies two communities as seen in fig:karateClubCommunities.
Only the node 10 is misidentified by our algorithm.

There is a tie-situation among the benefit scores
exhibited to node 10 by its neighbors;
so with random selection among alternatives 
our algorithm sometimes selects the 
wrong community.
The community labels of all the other nodes 
are identified correctly with respect to 
ground-truth community structure.
 






    








 §.§ Large real-life networks


We run our   algorithm on large
real-life networks with ground-truth 
communities, provided by SNAP <cit.>. 
For comparative analysis, 
Newman's fast greedy algorithm 
(NM) <cit.>, 
Infomap 
(Inf) <cit.>, 
Louvain 
(Lvn) <cit.>,
Label Propagation 
(LPA) <cit.> and
neighborhood-strength driven LPA
() <cit.>
are also run on these networks.
Newman's algorithm is omitted for YouTube network 
due to its long execution time.
The results are presented in tbl:tableLargeNetworks.

There is no clear winner in tbl:tableLargeNetworks,
which is a good news for local algorithms.
That is, 
although the local algorithms cannot see the global picture, 
they perform good enough.

The number of detected communities by
, Infomap, LPA, and  are close to each other
and not far from the ground-truth.
There are exceptions;
on the YouTube network, all four detect too many communities.
On European-email network with 42 ground-truth communities, 
LPA merges many communities together and detects only 3 communities 
while the other three do a better job.
On DBLP and Amazon networks;
both Louvain and 
Newman's algorithm detect very few number of communities.
Louvain has the best detection on YouTube network, 
while Newman's algorithm 
experiences performance problems.
Our  algorithm 
performs well on most of the networks. 
However, 
it performs poorly on YouTube network, 
which has the smallest clustering coefficient 
of these four networks.

Considering NMI values of all six algorithms,
it is possible that YouTube network may have subtle community structure.
On this network, the best performing algorithm, Infomap,
only gets NMI value of 0.13.
On DBLP and Amazon networks;
Infomap, LPA,  and our algorithm obtain similar NMI values, and 
they are much better than Louvain and Newman's algorithm.
On European-email network, 
local algorithms like LPA,
 and ours are not good enough.
It is possible that the network is not a good one for local approaches.
On all of the networks,  has highest 
execution times among the local algorithms.
Its execution time on YouTube network is very high compared to our algorithm and LPA.

For all the real-life networks, we use the provided 
ground-truth community structure to evaluate the quality of partitions found by 
each algorithm.
However, there is no single algorithm that performs good on all networks or there is not 
a single network on which some algorithms perform very good.
This may be due to the fact that supposed ground-truth for these networks 
do not reflect the original ground-truth community structure or 
show different aspects of the network structure, 
as discussed in the work of 
Peel et al. <cit.>.
For this reason, our test on real-life networks gives 
an idea about the relative performance of
algorithms compared to each other on different networks;
but does not lead to a conclusion on
whether they perform well on these networks or not.






 §.§ Generated networks



We test our algorithm, ,
also on generated LFR networks 
of 1,000 and 5,000 nodes
as reported in fig:LFR1000_NMI and fig:LFR5000_NMI, 
respectively.
The same algorithms 
that we run on real-life networks 
are also used for comparative analysis on these networks.
We also measure the execution times of 
the algorithms and report the results
in fig:LFR1000_executionTimes and 
in fig:LFR5000_executionTimes.
We present the details of the results on LFR 
networks of 5,000 nodes in tbl:tableLFRLarge.
For each parameter set, 
we generate 100 LFR networks for a given μ and 
run algorithms on all these datasets and
then average the results for each algorithm.

On LFR networks with 1,000 nodes, our  algorithm
is the best algorithm with Infomap when 0.1<μ<0.5.
For 0.5<μ<0.8, 
our algorithm is in the second place after Infomap.
When μ>0.7, most of the algorithms tend to find 
a small number of communities while our algorithm 
still identifies a reasonable set of communities.
LPA and LPAc find a single community 
that leads to the NMI value of 0.
Louvain and Newman's 
algorithm also find very few number of communities on these networks.


 








 


 
The second set of test is performed on LFR networks of 5,000 nodes.
Infomap, LPA, and LPAc are successful 
in identifying communities when mixing parameter is low, 
however, their quality degrades with increasing mixing parameter.
LPAc and LPA have slightly better results on
 the networks of 5,000 nodes generated with 0.4<μ<0.6
compared to the previous set of networks of 1,000 nodes.
With increasing value of the μ, performances of LPA and LPAc get 
worse and they tend to find a single community after μ>0.7.
Infomap has the similar tendency but has better results on 
LFR networks of 5,000 
nodes compared to previous 
set of networks of 1,000 nodes.
Newman's algorithm and Louvain 
find a small number of communities; 
they tend to merge communities, 
which may lead to a resolution limit <cit.>.
	
Our  algorithm identifies communities with 
high accuracy when μ is low.
It is the only algorithm to identify communities 
when community identification becomes very hard,
i.e.,
μ>0.75.
Its execution times are lower than most of the algorithms;
only LPA has better execution times.
However, considering the quality of identified communities
and corresponding execution times,
 algorithm performs better than LPA.
Newman's algorithm and  have 
the highest execution times on these networks.

 





§ CONCLUSION


We propose a new local community detection algorithm, ,
which is based on identifying borderlines of communities using boundary nodes in the network.
It is a local algorithm that is able to run on very large 
networks with low execution times.
It can identify communities with high quality, 
regardless of the network size.
 


On the networks with subtle community structure,
it outperforms other algorithms.
On these networks;
Infomap, LPA, and  merge all the nodes into a single community.
This is due to the heuristics of these algorithms, 
where they lose granular structures and 
fail to identify communities for certain kinds of networks.

However, our approach keeps granular 
communities by focusing on the similarity of nodes
even when it has many dissimilar neighbors
but only a few similar ones.
It does not force small communities to join
to a giant component.
Our algorithm performs successfully 
on generated networks with planted 
community structure, 
i.e.,
ground-truth is known.
However, on real-life networks 
where ground-truth is created by using some meta-data,
all of the algorithms in benchmark find different results.
This may be due to the fact that 
meta-data does not reflect the actual ground-truth 
communities or meta-data shows 
different aspects of the network structure as 
discussed in the work of Peel et al. <cit.>.


With its local approach,  is scalable
and suitable for distributed and parallel processing
(we have not 
implemented a parallel version for this paper).
Community detection task can be split into separate subtasks
on many computation devices (with the necessary piece of network data), 
which will enable
real-time community detection on very large networks.



The source code of the algorithm is available at:
https://github.com/murselTasginBoun/CDBN





§ ACKNOWLEDGMENTS


Thanks to 
Mark Newman, 
Vincent Blondel and 
Martin Rosvall 
for the source codes of their community detection algorithms. 
Thanks to 
Mark Newman, 
Jure Leskovec and 
Vladimir Batagelj 
for the network datasets.

This work was partially supported 
by the Turkish State Planning Organization (DPT) TAM Project (2007K120610).






  




