Social Network Analysis and Mining manuscript No. [630231]

Social Network Analysis and Mining manuscript No.
(will be inserted by the editor)
Identifying Community Structures in Dynamic Networks
Hamidreza Alvari1
Alireza Hajibagheri1
Gita Sukthankar1
Kiran Lakkaraju2
Received: December 11, 2015. Accepted: August 31, 2016.
Abstract Most real-world social networks are inher-
ently dynamic, composed of communities that are con-
stantly changing in membership. To track these evolv-
ing communities, we need dynamic community detec-
tion techniques. This article evaluates the performance
of a set of game theoretic approaches for identifying
communities in dynamic networks. Our method, D-GT
(Dynamic GameTheoretic community detection), mod-
els each network node as a rational agent who period-
ically plays a community membership game with its
neighbors. During game play, nodes seek to maximize
their local utility by joining or leaving the communi-
ties of network neighbors. The community structure
emerges after the game reaches a Nash equilibrium.
Compared to the benchmark community detection meth-
ods, D-GT more accurately predicts the number of com-
munities and nds community assignments with a higher
normalized mutual information, while retaining a good
modularity.
Keywords community detection
dynamic social
networks
game-theoretic models
Research at University of Central Florida was supported by
NSF award IIS-0845159. Sandia National Laboratories is a
multi-program laboratory managed and operated by Sandia
Corporation, a wholly owned subsidiary of Lockheed Martin
Corporation, for the U.S. Department of Energy's National
Nuclear Security Administration under contract DE-AC04-
94AL85000.
1University of Central Florida, Orlando, Florida,
{halvari,hajibagheri,gitars}@eecs.ucf.edu
2Sandia National Labs, Albuquerque, New Mexico,
klakkar@sandia.gov1 Introduction
The natural
ux of people's changing social ties and
interests generates a dynamic social network. This in-
visible network can be observed by capturing daily or
weekly snapshots of user activities on social media plat-
forms and massively multiplayer online games (MMOGs).
It is informative to study changes in the network at the
community level , as well as the individual level. Com-
munities are emergent groups that are created as peo-
ple form highly connected subnetworks with their fam-
ilies, co-workers, and friends. Often communities are
formed by participants with the same goals, interests,
or a geographic location. For instance, in MMOGs, net-
work communities may emerge from guilds of players
with common economic interests or alliances who share
strategic goals. As the network changes, user groups can
grow, shrink, or disappear, causing drastic changes in
the total number of network communities.
Community detection can help us understand the
hidden social structure of the user populations, but the
dynamic aspect of networks can pose problems for stan-
dard algorithms. Our method uses stochastic optimiza-
tion to nd the best community structure, assuming
that the nodes are modeled as rational players who seek
to maximize their personal utility while playing a com-
munity membership game with neighboring nodes. In
this game, the active agent decides to join or leave dif-
ferent communities; agents receive benets from being
part of the same community as their network neighbors
but are penalized for joining too many communities.
The Nash equilibrium of the current game corresponds
to the community structure of the current snapshot. As
the network evolves, agents usually nd it advantageous
to modify their community membership strategy. This
article examines the performance of varying the amountarXiv:1609.02622v2 [cs.SI] 12 Sep 2016

2 Alvari et al_
of information propagated from prior snapshots. Even
in dynamic networks, there are many nodes that retain
the same community membership or rejoin their for-
mer communities. Thus propagating information from
previous snapshots can provide more favorable initial-
ization conditions for the stochastic optimization pro-
cedure.
Much of the power of the D-GT framework (orig-
inally introduced in (Alvari et al., 2014a)) lies in its
potential for customization; however, without guidance
end users can be overwhelmed by myriad choices. Our
aim in this article is to present a comprehensive anal-
ysis of the algorithm's performance in common sce-
narios; while retaining the same basic game-theoretic
model, we evaluate dierent variations of our proce-
dure. First, we examine the performance of dierent
utility functions, a similarity-based utility function (Al-
vari et al., 2011) vs. the use of a personalized modularity
function (Chen et al., 2010). Then we compare dier-
ent initialization approaches in which the following in-
formation is propagated: 1) no information ( D-GTS );
2) the union of the community membership informa-
tion over all snapshots ( D-GT ); 3) community mem-
bership information from the previous snapshot ( D-
GTP ); 4) ground truth information for a small seed
set (D-GTG ). Our game-theoretic model is robust to
minor changes in the procedure and most variants out-
perform the benchmarks.
Our experiments were conducted on networks cre-
ated from dierent dynamic processes: internet routers
(AS-Oregon Graph, the AS-Internet Routers Graph),
shifting organization structure (Enron Email dataset),
citation graphs from arXiv (hep-ph), and player in-
teractions in massively multiplayer online games (Tra-
vian Messages, Travian Trades). Results were compared
against ve other methods: LabelRankT, iLCD, OSLOM,
InfoMap and Louvain in terms of normalized mutual
information (NMI), modularity, and the number of de-
tected communities. The next section presents an over-
view of related work on community detection in dy-
namic networks. Section 3 describes our problem for-
mulation and our proposed method ( Dynamic Game
Theoretic community detection). Experimental results
are provided in Section 4, before we conclude the article
(Section 5).
2 Related Work
The problem of community detection has been widely
studied in the literature compared to the other research
areas in the social networks (Yang and Leskovec, 2010;
Beigi et al., 2016c; Leskovec et al., 2010; Beigi et al.,
2016b,a). In particular, in static networks, communitydetection has appeared in multiple disciplines includ-
ing sociology and computer science. This has yielded
a diverse set of approaches ranging from traditional
network structure based algorithms (Girvan and New-
man, 2002; Newman, 2006, 2004), optimization tech-
niques (Alvari et al., 2011; Chen et al., 2010), label
propagation (Raghavan et al., 2007; Xie and Szyman-
ski, 2011, 2012), propinquity (Zhang et al., 2009) and
information diusion (Hajibagheri et al., 2013, 2012).
Detecting community structure in dynamic networks,
on the other hand, has attracted less research atten-
tion due to the complexity of the problem and dearth
of good datasets. There are some community detec-
tion algorithms originally design-ed for static networks
that continue to perform well in dynamic datasets. For
instance, Lancichinetti et al.'s OSLOM (Order Statis-
tics Local Optimization Method) works on single snap-
shots but also benets from information from previous
network partitions. Like D-GT, OSLOM's optimization
procedure can be initialized with the partition from
the previous snapshot; it aims to optimize cluster sig-
nicance with respect to a global null model (Lanci-
chinetti et al., 2011). We use this method as one of our
benchmarks, along with two other static community de-
tection algorithms, Louvain (Blondel et al., 2008) and
InfoMap (Rosvall and Bergstrom, 2008). These algo-
rithms perform well on many static community detec-
tion problems and have the benet of being fast to com-
pute on a single network snapshot.
Other network properties have also been used to
perform dynamic community detection; for instance Hui
et al. (2007) proposed a distributed method for com-
munity detection in which modularity was used as a
measure instead of the objective function. QCA (Quick
Community Adaptation) is a modularity-based approach
that focuses explicitly on the changes in the network
structure, rather than recomputing community struc-
ture from scratch at each time step (Nguyen et al.,
2014). In this article, we evaluate the use of personal
modularity as an alternative gain function to neighbor-
hood similarity.
Some studies have focused on studying the evolution
of communities over time. For instance, Hopcroft et al.
(2004) identied subsets of nodes, \natural communi-
ties", that were stable to small perturbations of the in-
put data. Communities detected in later snapshots were
matched to earlier snapshots using the natural commu-
nity tree structure. Palla et al. (2009) proposed an in-
novative method for detecting communities in dynamic
networks based on the k-clique percolation technique;
in their approach, communities are dened as adjacent
k-cliques, that share k1 nodes.

Identifying Community Structures in Dynamic Networks 3
Machine learning has also been employed to model
changes in community structure; for instance, Takaoli
et al. (2014) predict transitions in community structure
by learning supervised machine learning classiers. This
requires data on past transitions to train the classiers,
which limits its applicability to certain datasets. Sun
et al. (2007) adopt a data mining approach to detect
clusters on time-evolving graphs; community discovery
and change detection are performed using the minimum
description length (MDL) paradigm.
Rather than independently detecting communities
at each snapshot and matching them, another option
is to make a local decision to add nodes to existing
communities when new edges appear in the network.
One of our benchmarks, iLCD (intrinsic Longitudinal
Community Detection) (Cazabet et al., 2010), updates
the community structure of the network based on time-
stamped sets of edges. Nodes are added to communi-
ties if its mean number of second neighbors and robust
second neighbors exceeds the current average for the
community. However, this model is limited to certain
types of network changes, and cannot handle intercon-
nected pairs of nodes being simultaneously added or the
removal of edges.
Optimization can be used to identify minimum cost
community assignments in dynamic graphs. FacetNet
(Lin et al., 2008) is a framework for analyzing commu-
nities in dynamic networks based on an optimization of
snapshot costs. It is guaranteed to converge to a local
optimal solution; however, its convergence speed is slow,
and it needs to be initialized with the number of com-
munities which is usually unknown in practice. Folino
and Pizzuti (2014) modeled dynamic community detec-
tion as a multi-objective optimization problem. Their
approach is parameter free and uses evolutionary clus-
tering to optimize a dual objective function. The rst
objective selects for highly modular structures at the
current time step, and the second minimizes the dier-
ences between community structures in the current and
previous time steps. D-GT also uses a stochastic opti-
mization procedure, but all of the agents individually
optimize their utilities based on local network informa-
tion.
The Markov Cluster Algorithm (MCL) (Van Don-
gen, 2000) identies graph clusters by computing the
probabilities of random walks through the graph;
ow
simulations are performed by alternating expansion (ma-
trix squaring) with in
ation operations (Hadamard pow-
ers). Due to its mathematical simplicity, it is popu-
lar for community detection in many domains but is
slow and often overestimates the number of commu-
nities in the dataset. Regularized-MCL (Satuluri and
Parthasarathy, 2009) is a variant of MCL that preventsovertting by taking into account neighbor
ows. It can
also be used within a multi-level framework (Multi-level
Regularized MCL) to speed up computation by execut-
ing a sequence of coarsening operations on the graph
before executing R-MCL.
LabelRankT (Xie et al., 2013), shares some similari-
ties with the MCL techniques described above while im-
proving upon them in several ways; it is a label propaga-
tion approach in which the in
ation operation is applied
to the label distribution matrix rather than to the adja-
cency matrix. Each node requires only local information
during propagation making it more scalable than MCL
and amenable to parallelization. Due to LabelRankT's
strong performance and good implementation, it was
selected as the best label propagation benchmark for
our work.
Our proposed method (D-GT) attempts to simu-
late the decision-making process of the individuals cre-
ating the communities, rather than focusing on statis-
tical correlations between labels of neighboring nodes.
We believe that exploiting game theory for dynamic
community detection yields more realistic, ne-grained
communities since intrinsically game theory is a good
representation for expressing the behavior of individ-
uals and strategic interactions among them (Adjeroh
and Kandaswamy, 2007).
In previous work, we have demonstrated the suc-
cess of game-theoretic approaches in static community
detection across several domains, including detecting
guilds in massively multiplayer online games (Alvari
et al., 2014b) and predicting trust between users on
e-commerce sites (Beigi et al., 2014). Many of these do-
mains featured overlapping communities in static net-
works (Alvari et al., 2011, 2013); however in this arti-
cle the datasets are dynamic, but not overlapping. D-
GT makes a hard assignment at the termination of the
stochastic optimization procedure by selecting the com-
munity assignment with the highest utility function. In
this article, we investigate the performance of dierent
gain functions and initialization procedures, on a va-
riety of evaluation metrics (modularity, NMI, number
of detected communities). The strength of the D-GT
framework is its versatility; our results show that sub-
stantial performance improvements can be achieved by
customizing it for the problem at hand.
3 Method
First, we provide the formal denition of the problem
and the notations used throughout the paper. Given
snapshots T=fTtj8t;t= 1;:::;Mgof a dynamic net-
work and their corresponding underlying graphs Gt=
(Vt;Et), withnt=jVtjvertices and mt=jEtjedges,

4 Alvari et al_
Table 1: Denition of Symbols.
Symbol Denition
T set of snapshots
C set of communities
Gtgraph oft-th snapshot with no self-edges
Ctcommunity structure of t-th snapshot
Ct
kk-th community in Ct
mt,ntnumber of edges and vertices of Gt
Atadjacency matrix of Gt
Stprole of strategies of t-th snapshot
st
ii-th agent's strategy in t-th snapshot
gt
ii-th agent's gain function in t-th snapshot
lt
ii-th agent's loss function in t-th snapshot
ut
ii-th agent's utility function in t-th snapshot
ct
ij similarity between i-th andj-th agents
in thet-th snapshot
Table 2: Denition of Possible Actions.
Action Denition
Join add a new label to st
i
Leave remove a label from st
i
Switch remove a label from st
iand add a new one
No operation no action is performed
where t=1,…,M, we aim to detect community structure
C=fCtj8t;t= 1;:::;Mgof the network. Table 1
shows the symbols and denitions used throughout the
paper.
We leverage a dynamic agent-based model to detect
communities by optimizing each user's utility through
a stochastic search process (Alvari et al., 2011). In this
article, we evaluate four dierent variants of the pro-
cedure: D-GT ( Dynamic GameTheoretic community
detection), D-GTP ( D-GT with passing one Previous
Snapshot) D-GTS ( D-GT with Separate Runs) and
D-GTG ( D-GT with passing Ground Truth).
3.1 Dynamic Game Theory (D-GT)
In this section, we present the framework for D-GT. We
treat the process of community detection as an iterative
game performed in a dynamic multi-agent environment
in which each node of the underlying graph is a selsh
agent who decides to maximize its total utility ui. Note
that hereafter we use the terms node,user, and agent
interchangeably. The terms pool,list, or setof agents
are used to denote the set of nodes maintained during
each game.
During the community formation game, each agent
assesses whether taking an action ( join,switch , orleave )
(Table 2) will increase its utility. An agent joins a
new community ctCtby adding its label to st
i. Itthen gains utility ut
Joinand its community membership
changes:
st
i st
i[fctg: (1)
It may leave one of its own communities, say c0tby
removing its label from st
iwhich results in utility ut
Leave
and changes the community membership as follows:
st
i st
i=fc0tg: (2)
The agent can also simultaneously switch communities:
st
i st
i=fc0tg;st
i st
i[fctg: (3)
Even though the switch action is not strictly necessary,
having this additional action speeds up the convergence
of the stochastic search process.
The new utility u0t
ifor this agent is updated as fol-
lows:
u0t
i maxfut
Join;ut
Leave;ut
Switch;ut
noOpg: (4)
To reduce computation time, only communities con-
taining the agent's nearest network neighbors are con-
sidered as candidates for the join/switch operation, and
we independently identify the best communities for the
join and leave operations. If no action improves the
agent's utility, it does not change its strategy ( no oper-
ation ).
The set of all communities at the t-th snapshot
is denoted by Ct. We dene a strategy prole St=
(st
1;st
2;:::;st
n) which represents the set of all strategies
of all agents, where st
iCtdenotes the strategy of
agenti, i.e. the set of its labels at snapshot t. In our
framework, for each snapshot, the best response strat-
egy of an agent iwith respect to strategies St
iof other
agents is calculated as:
arg max
st
iCtut
i(St
i;st
i) (5)
Agents are selected randomly, without replacement, un-
til all the agents have had the opportunity to play the
community formation game in order to guarantee ad-
equate exploration of the strategy search space. The
utility function for each agent is calculated by combin-
ing the benet of its community memberships, based
on a gain function and subtracting losses incurred:
ut
i(St
i;st
i) =gt
i(St
i;st
i)lt
i(St
i;st
i); (6)
We have experimented with two variants on the gain
function for agent i.1The rst gain function is based
onsimilarity between agents:
gt
i(St) =1
mtX
k2st
iX
j2Ct
k;j6=ict
ij: (7)
1We employ the notation for directed graphs, although it is
straightforward to generalize to undirected graphs by ignoring
thein/out superscripts.

Identifying Community Structures in Dynamic Networks 5
Here, we use neighborhood similarity to quantify the
structural equivalence between users at time t:
ct
ij=8
>>><
>>>:wt
ij(1din;t
idout;t
j=2mt)At
ij= 1;wt
ij>= 1
wt
ij=ntAt
ij= 0;wt
ij>= 1
din;t
idout;t
j=4mtAt
ij= 1;wt
ij= 0
din;t
idout;t
j=4mtAt
ij= 0;wt
ij= 0(8)
wt
ijis dened as the number of common neighbors pos-
sessed by nodes iandj, where common neighbors are
nodes with direct in-edges from both iandj.din;t
iand
dout;t
iare the in- and out-degrees of node iat snapshot
t.mtandntare the number of edges and nodes respec-
tively and primarily serve as normalization constants.
Note thatct
ijassumes its highest value when two nodes
have at least one common neighbor and are also directly
connected, i.e. At
ij= 1. Hence agents playing the com-
munity formation game benet from joining commu-
nities containing connected nodes with many common
neighbors.
The second gain function measures the personalized
modularity of thei-th agent:
gt
i(St) =1
2mtX
k2st
iX
j2Ct
k;j6=iX
k02st
j(At
ij(i;j)din;t
idout;t
j
2mtjk\k0j);(9)
wherek2st
iandk02st
jrefer to the community labels
at snapshot tthat agentiandjbelong to respectively;
(i;j) is an indicator function that is 1 when iandj
are members of the same community. More intuitively,
this gain function explains how well the i-th agent ts
the communities it belongs to, compared to a randomly
assigned community.
Similar to what happens in real life, we also consider
the loss function lt
ifor each agent, which is linear in the
number of labels each agent has, This can be used to
model the intrinsic communication overhead of belong-
ing to multiple communities and prevents the agents
from indiscriminately joining every available commu-
nity. Therefore we dene the following loss function for
agenti:
lt
i(St
i;st
i) =jst
ij
mt: (10)
Herest
i=f1;2;:::;kgis the set of labels at snapshot
twhich agent ibelongs to.
In our framework, the best response strategy of the
agentiwith respect to strategies St
iof other agents is
calculated by:
arg max
s0t
iCtgt
i(St
i;s0t
i)lt
i(St
i;s0t
i): (11)
The strategy prole Stforms a pure Nash equi-
librium of the community formation game if no agentcan unilaterally improve its own utility by changing its
strategy:
8i;s0t
i6=st
i;ut
i(St
i;s0t
i)ut
i(St
i;st
i): (12)
A local equilibrium is reached if all agents play their
local optimal strategies:
8i;s0t
i2ls(st
i);ut
i(St
i;s0t
i)ut
i(St
i;st
i): (13)
Herels(st
i) refers to local strategy space of agent i,
which is the set of possible label sets it can obtain by
performing the actions dened earlier.
3.2 Existence of Equilibria
The evolving community structure present in dynamic
networks is accounted for by propagating strategies from
prior snapshots. D-GT uses the same community forma-
tion game described in Alvari et al. (2013). Since strat-
egy propagation only changes the initialization condi-
tions, the same proof of the existence of Nash equilibria
in the community formation game applies to D-GT as
well; we summarize the argument below.
To see when a certain game has Nash equilibria, re-
call that potential games are a general class of games
that permit pure Nash equilibria (Nisan et al., 2007).
For any nite game, there exists a potential function 
dened on the strategy prole Sof the agents that maps
this prole to some real values. This function must val-
idate the following condition:
8i;(St)(St
i;s0t
i) =ut
i(St
i;s0t
i)ut
i(St):
(14)
Equivalently, if the current strategy prole of the
game isStand the agent iswitches from strategy st
ito
s0t
i, the potential function exactly mirrors the changes
in the agent utility. It is not hard to see that a game
has at most one potential function. A game that does
possess a potential function is called a potential game.
Consequently we have the following theorem:
Theorem 1. Every potential game has at least one
pure Nash equilibrium, namely the strategy prole
Sthat minimizes (S) (Nisan et al., 2007).
Proof. Letbe a potential function for this game and
letSbe a pure strategy prole minimizing (S).
Consider any action performed by player ithat re-
sults in a new strategy prole S0. By assumption,
(S0)(S) and by the denition of a potential
function,ui(S0)ui(S) =(S)(S0). Thus the
utility of agent icannot increase from this move and
henceSis stable (Chen et al., 2010).

6 Alvari et al_
Now we provide a sucient condition to prove our
community formation game as a potential game and
thus address the existence of the Nash equilibrium. First
we have the following denition (Chen et al., 2010):
Denition [Locally linear function ].A set of func-
tionsffi;1ingis locally linear with locality
factorif for every strategy prole S the following
condition holds:
8i;fi(Si;s0
i)fi(S) =(f(Si)f(S)):
(15)
wheref(:) =P
i2[n]fi(:). According to Theorem 2, if
we show that our gain and loss functions are locally
linear, then we can prove the existence of Nash equilib-
rium in our framework.
Theorem 2. Letfgi;1ingandfli;1ingbe
the sets of gain and loss functions of a community
formation game. If these sets are locally linear func-
tions with linear factors GandL, then the com-
munity formation game is a potential game (Nisan
et al., 2007).
Proof. We dene a potential function as (St) =ll(St)
gg(St) and assume that agent iwho changes its
strategy from st
itos0t
i. Based on the denitions of lo-
cally linear functions and the utility functions ut
i(:),
we have(St)(St
i;s0t
i) =ut
i(St
i;s0t
i)ut
i(St).
Therefore, the community formation game is a po-
tential game (Chen et al., 2010).
3.3 Algorithm
An overview of the D-GT framework is shown in Al-
gorithm 1. For every snapshot of the network, a set
of agents, one representing each node in the graph, is
created to play the community formation game. The
community structure is initialized either with a set of
singleton communities or with communities passed from
previous snapshots. During game play, an agent is ran-
domly selected (without replacement) from the pool; it
selects an action (join, leave, switch, or no op) by calcu-
lating the strategy that yields the highest utility. After
the agent plays, the community structure is updated.
The game is played until the number of agents chang-
ing their play strategy between permutations falls be-
low the threshold, or the maximum iteration is reached.
Empirically, we have discovered that 8 nis a good itera-
tion limit with a threshold of 5%. Thus if there are 1000
nodes in a network snapshot, the community formation
game is played until fewer than 50 nodes change strate-
gies or to the maximum of 8000 games. Figure 1 shows
an example of the convergence in utility vs. iteration.
Fig. 1: Change in average utility summed over all nodes
vs. iteration for the Travian-Trades dataset (one snap-
shot with 964 nodes). The algorithm converges after
6680 iterations which requires 2.8 seconds to complete.
The outer loop of the algorithm requires iterating
overMgraph snapshots, and the inner loop requires
performing a maximum of 8 niterations of the com-
munity formation game that, in the worst case, re-
quires considering ncommunity choices. Thus, the over-
all time complexity of D-GT is O(Mn2).
D-GT maintains a candidate set of multiple com-
munity assignments per agent until the last iteration
and then selects the assignment with the highest utility
function as the nal disjoint partition. In this article,
we evaluate several dierent variants of the procedure:
{ D-GTS (D-GT with Separate runs): this version
does not employ any information from previous runs
and hence is equivalent to a static community de-
tection procedure.
{ D-GTP (D-GT passing one Previous Snapshot):
rather than passing strategy proles from all pre-
vious snapshots, we only initialize the community
formation game with the structure from a single pre-
vious time slice. For each snapshot Tk, we initialized
communities and agents to the existing information
fromTk1.
{ D-GTG (D-GT with passing Ground Truth): D-
GTG leverages some ground truth information. A
select seed group of ground truth communities with
predened size is used to initialize communities for
snapshotTk; however we do not pass any discov-
ered community structure to the following snapshots
(similar to D-GTS). This variation cannot be used
unless some of the agents' community membership
is known in advance.

Identifying Community Structures in Dynamic Networks 7
Algorithm 1 D-GT Community Formation Game
1:Input : Snapshots T=fT1;T2;:::;TMg
2:Output: Communities C=fC1;C2;:::;CMg
3:for allTt2T do
4: Initialize p 0
5:repeat
6: Initialize q 0
7: for all agents in randomized order do
8: Select best action ausing Eqn. 5
9: ifa= \No operation" then
10: q q+ 1
11: else
12: Update Ctaccording to a
13: end if
14: end for
15:p p+ 1
16: untilp>8 orq>threshold
17:end for
4 Experimental Results
Algorithms were evaluated together on a system with
12G of RAM and Intel CPU 2.53 GHz, and all reported
results were averaged over ten repetitions. We compare
D-GT with the following community detection base-
lines:
{ LabelRankT2(Xie et al., 2013). LabelRankT
functions according to the generalized LabelRank,
in which each node requires only local information
during label propagation processing. Several param-
eters must be set before running the algorithm on
the data; we used the best performing values re-
ported in the original paper.
{ iLCD3(Cazabet et al., 2010). iLCD is another
well known community detection approach for dy-
namic social networks which works by rst adding
edges and then merging the similar ones. It takes
the dynamics of the network into account.
{ OSLOM4(Lancichinetti et al., 2011). The Or-
der Statistics Local Optimization Method (OSLOM)
is a versatile community detection algorithm that
can handle most types of graph properties includ-
ing edge directions and weights, overlapping com-
munities, hierarchies and community dynamics. It
is based on the local optimization of a tness func-
tion expressing the statistical signicance of clusters
with respect to random
uctuations.
{ InfoMap5(Rosvall and Bergstrom, 2008). In-
foMap is a static community detection method that
calculates the probability
ow of random walks and
decomposes the network into modules by compress-
2https://sites.google.com/site/communitydetectionslpa
3http://www.cazabetremy.fr/iLCD.html
4http://www.oslom.org/software.htm
5http://www.mapequation.org/code.htmling a description of the
ows. Since this is a static
algorithm, we run it separately on each snapshot.
{ Louvain6(Blondel et al., 2008). The Louvain
method is a static community detection approach
designed to optimize modularity using heuristics.
Small communities are found by optimizing mod-
ularity locally for all nodes. Then each community
is grouped into a single node, and the rst step is
repeated. We run this algorithm separately on every
network snapshot.
4.1 Datasets
To illustrate the strength and eectiveness of our ap-
proach, we selected some communication networks from
the SNAP7graph library as well as two networks (mes-
sages and trades) from a well-known multiplayer online
game. Statistics for the datasets are provided in Table 3,
and description of the datasets is as follows:
AS-Oregon Graph (Leskovec et al., 2005) .
The dataset contains 9 graphs of Autonomous Systems
(AS) peering information inferred from Oregon route-
views between March 31, 2001 and May 26, 2001. These
9 graphs are dierent snapshots from the data with a
minimum of 10,670 and maximum of 11,174 nodes. The
number of edges ranges from 21,999 in the snapshot
of April 07, 2001 to 23,409 in May 26, 2001. Figure 2
shows the number of edges added and deleted, as well
as the number of nodes involved in the changes for the
AS-Oregon dataset.
AS-Internet Routers Graph (Leskovec et al.,
2005) . Similar to AS-Oregon, this is a communication
network of who-talks-to-whom from the Border Gate-
way Protocol logs of routers in the Internet. The dataset
contains 733 daily snapshots for 785 days from Novem-
ber 8, 1997 to January 2, 2000. The number of nodes
in the largest snapshot is 6,477 (with 13,233 edges).
Figure 3 illustrates that the structure of the graph can
change dramatically at each snapshot.
Enron Email (Sun et al., 2007) . The Enron
email network contains email message data from 150
users, mostly senior management of Enron Inc., from
January 1999 to July 2002. Each email address is rep-
resented by an unique ID in the dataset, and each link
corresponds to a message between the sender and the
receiver. After a data renement process, we simulate
the network evolution via a series of 12 growing snap-
shots from January 2000 to December 2000. Enron net-
work changes are shown in Figure 4.
6https://sites.google.com/site/ndcommunities
7http://snap.stanford.edu/

8 Alvari et al_
Fig. 2: The structural changes in the AS-Oregon dataset over 9 snapshots including the number of edges deleted
(E) and added ( E+), as well as the number of nodes involved in changes ( N+). The community detection
problem becomes more challenging when there are signicant structural changes between snapshots.
Fig. 3: The structural changes in the AS-Internet dataset over 733 snapshots.
Fig. 4: The structural changes in the Enron dataset over 12 snapshots.
Fig. 5: The structural changes in the Travian Trades dataset over 30 snapshots.
Fig. 6: The structural changes in the Travian Messages dataset over 30 snapshots.

Identifying Community Structures in Dynamic Networks 9
Fig. 7: The structural changes in hep-ph dataset over 10 snapshots.
Table 3: Dataset Summary
Data Oregon Internet Enron Travian (Messages) Travian (Trades) hep-ph
Min # of nodes 10,670 2,948 101 1,373 964 12,711
Max # of nodes 11,174 6,477 137 2,100 1,336 34,401
Min # of edges 21,999 3,386 1,432 8,511 8,080 39,981
Max # of edges 23,409 13,233 5,015 19,242 10,221 51,485
# of snapshots 9 733 12 30 30 10
Travian8(Hajibagheri et al., 2015) Travian is a
popular browser-based real-time strategy game with more
than 5 million users. Players seek to improve their pro-
duction capacity and construct military units in order
to expand their territory through a combination of col-
onization and conquest. Each game cycle lasts a xed
period (a few months) during which time the players
vie to complete construction on one of the Wonders of
the World. To do this, they form alliances of up to 60
members under a leader or a leadership team; in this
article these alliances are used as the ground truth for
evaluating the community detection procedure.
Travian has an in-game messaging system (IGM)
for player communication which was used to create our
Messages network. Each player can submit a request to
trade a specic resource. If another player nds this re-
quest interesting, he/she can accept it and the trade will
occur; this data was used to build the Trade network.
About 70% of messages are exchanged between users in
the same alliance (community) making it more predic-
tive of community structure than the Trades network
since only 30% of edges in this network represent trades
occurred between players within the same alliance. The
structural changes in both Travian datasets are shown
in Figures 5 and 6.
HEP-PH Citation Graph (Leskovec et al., 2005) .
The HEPPH (high energy physics theory) citation graph
from the e-print arXiv covers all the citations within a
dataset ofn= 29;555 papers with e= 352;807 edges.
If a papericites paper j, the graph contains a directed
edge fromitoj. If a paper cites, or is cited by, a pa-
8ial.eecs.ucf.edu/travian.phpper outside the dataset, the graph does not contain any
information about this. This data covers papers in the
period from January 1993 to March 2002. There are
ten snapshots where each snapshot includes data from
twelve months except the last snapshot which only con-
tains edges from the rst three months of 2002 (Fig-
ure 7).
4.2 Metrics
We evaluated the performance of all methods using the
following metrics.
4.2.1 Normalized Mutual Information
One way to measure the performance of a community
detection algorithm is to determine how similar the par-
tition delivered by the algorithm is to the desired par-
tition, assuming ground truth information about the
community membership exists. Out of several existing
measures (Fortunato, 2010), we selected the standard
version of normalized mutual information (NMI) (Danon
et al., 2005), which is computed as follows:
Inorm(X,Y) =2I(X;Y )
H(X) +H(Y);
(16)
whereI(X;Y ) is mutual information between two ran-
dom variables XandY(i.e. two community parti-
tions) (MacKay, 2003):

10 Alvari et al_
I(X,Y) =X
xX
yP(x;y) logP(x;y)
P(x)P(y);
(17)
HereP(x) indicates the probability that X=xand
joint probability P(x;y) equals to P(X=x;Y =y).
H(X) andH(Y) are the entropies of XandY, respec-
tively. NMI lies in the range [0,1], equaling one when
two partitions XandYare exactly identical and zero
when they are totally independent. Code to calculate
NMI can be downloaded at: https://sites.google.
com/site/andrealancichinetti/software .
4.2.2 Modularity
Modularity measures the dierence between the num-
ber of intra-community edges for a given community
partition vs. a random distribution of edges; it is the
most popular qualitative measure in detecting commu-
nities in social networks. However, it has been shown
that modularity has drawbacks and becomes unreliable
when networks are too sparse (Fortunato and Barthelemy,
2007). It is also useful to examine the number of de-
tected communities in conjunction with modularity to
ensure that the algorithm is not being overly aggressive
about combining small communities in order to maxi-
mize overall network modularity.
Standard modularity Qis usually dened as follows:
Q=1
2mX
ij[Aijdidj
2m]ci;cj (18)
where Aijis an element of the adjacency matrix, ij
is the Kronecker delta symbol, and ciis the label of
the community to which vertex iis assigned. However,
modularity can be slightly dierent for directed net-
works (Leicht and Newman, 2008) and can then be re-
formulated as:
Q=1
mX
ij[Aijdin
idout
j
m]ci;cj (19)
where Aijis dened in the conventional manner to be 1
if there is an edge from itojand zero otherwise. Here,
the probability of the existence of an edge from ver-
texito vertexjhas the probability din
idout
j=m, where
din
ianddout
jare the in- and out-degrees of the vertices
respectively.4.3 Evaluation
In this article, we examine four research questions:
1. how does the gain function in
uence community de-
tection performance?
2. does the initialization procedure aect the perfor-
mance of dynamic community detection?
3. how does D-GT perform vs. the competitor meth-
ods?
4. in cases where the community membership of a small
number of the agents is known, can it be used to im-
prove D-GT's performance?
We analyze the performance of the D-GT variants
vs. LabelRankT, iLCD, OSLOM, InfoMap, and Lou-
vain on the two metrics, normalized mutual informa-
tion (NMI) and modularity. We hypothesize that D-GT
with the modularity gain function will perform well on
the modularity evaluation metric, since its stochastic
search process essentially optimizes local modularity.
Also D-GT's initialization procedure will not necessar-
ily help the modularity optimization process since it
can be performed eectively without considering com-
munity evolution through time. This suggests that D-
GTS is a good candidate for the modularity evaluation
metric.
However, in most real-world communities, prior com-
munity membership is a good predictor of future mem-
bership. Thus we believe that D-GT is more eective at
discovering the real community structure as measured
by the normalized mutual information (NMI) evalua-
tion metric. Our previous work (Alvari et al., 2011) has
shown that the neighborhood similarity function is a
good gain function for recovering the true community
structure so we hypothesize that D-GT (similarity) is
the best choice for NMI.
Figure 8 shows the average performance of all the
D-GT variants with the similarity gain function vs.
OSLOM, LabelRankT, iLCD, InfoMap and Louvain.
Note that it is not possible to calculate the NMI per-
formance on the AS-Internet, AS-Oregon, Enron, and
hep-ph datasets since we don't have ground truth com-
munity structure; for the Travian datasets, we use the
alliance membership to calculate the NMI. D-GT (sim-
ilarity) outperforms all other methods ( p < 0:01) on
this metric.
In D-GT, each node's community membership vec-
tor is initialized as the superset of all communities that
it has been a member of at any time step. If most of the
nodes have remained within the same communities, the
correct structure is quickly discovered. In cases where
there are cyclic temporal patterns, there is clearly some
value in considering earlier community assignments,

Identifying Community Structures in Dynamic Networks 11
Table 4: Modularity evaluation metric on the six datasets; results are averaged over all snapshots.
Algorithm/Dataset Oregon Internet Enron Travian (Messages) Travian (Trades) hep-ph
D-GT + Similarity 0.610.02 0.590.02 0.500.02 0.450.03 0.430.02 0.560.03
D-GTS + Similarity 0.63 0.02 0.570.04 0.480.02 0.44 0.02 0.42 0.01 0.550.02
D-GTP + Similarity 0.590.02 0.580.05 0.470.03 0.44 0.03 0.41 0.02 0.510.04
D-GT + Modularity 0.570.03 0.550.04 0.470.03 0.48 0.04 0.41 0.02 0.550.04
D-GTS + Modularity 0.63 0.02 0.510.02 0.430.02 0.490.03 0.400.03 0.540.02
D-GTP + Modularity 0.590.03 0.480.03 0.390.02 0.47 0.03 0.42 0.02 0.520.04
OSLOM 0.490.05 0.520.04 0.390.03 0.44 0.04 0.32 0.01 0.490.01
LabelRankT 0.440.01 0.410.09 0.340.05 0.42 0.04 0.36 0.03 0.430.06
iLCD 0.150.05 0.110.01 0.130.05 0.19 0.02 0.09 0.01 0.160.07
InfoMap 0.63 0.04 0.610.01 0.490.08 0.51 0.02 0.43 0.04 0.560.04
Louvain 0.590.02 0.570.04 0.460.06 0.530.02 0.49 0.02 0.540.07
Fig. 8: Normalized mutual information (NMI) evaluation metric on the two Travian datasets with ground truth
community membership information; results are averaged over all snapshots. The variants of D-GT are colored in
purple, LabelRankT (red), OSLOM (indian red), iLCD (yellow), InfoMap (gray) and Louvain (blue).
As predicted it outperforms the more myopic D-
GTS (that uses no prior information) and D-GTP (one
previous snapshot); paired t-test comparisons on the
two Travian datasets are signicant at the p < 0:01
level. Figure 9 shows that D-GT (similarity) is more
successful than the other D-GT variants at correctly
predicting the number of communities, as measured by
summed absolute dierence between predicted and ac-
tual community numbers (lower is better). Note that
it is possible to do acceptably well on the NMI metric
while still incorrectly estimating the actual number of
communities in the dataset. OSLOM also performs well
on both metrics (NMI and number of communities).
It is also useful to look at how the number of pre-
dicted communities varies between consecutive snap-
shots. In most cases, the number of communities should
remain relatively stable, since the structure of real-world
communities rarely changes completely in short period
of time. This is denitely true in Travian, where the
number of alliances changes relatively slowly. Figure 10shows the number of predicted communities vs. time
on the Travian (Trades) dataset; all of the methods
make more consistent predictions over time than La-
belRankT.
Table 4 shows the average performance of all the D-
GT variants vs. OSLOM, LabelRankT, iLCD, InfoMap
and Louvain at optimizing modularity. Bold font shows
the absolute best performing algorithm, with italics mark-
ing the best performing D-GT variant. All D-GT vari-
ants are competitive at optimizing modularity but none
are exceptional. They outperform the other dynamic
algorithms (iLCD, LabelRankT) but rarely the static
community detection algorithms (Louvain and InfoMap).
This is unsurprising since the modularity metric does
not intrinsically reward preserving continuity between
snapshots. D-GT (similarity) continues to perform well,
as does D-GTS (modularity).
In some scenarios, it is plausible that the community
membership of a small number of agents is known in ad-
vance, and the community detection procedure should

12 Alvari et al_
Fig. 9: Absolute dierence between the predicted number of communities and the actual number for the two
Travian datasets. D-GT (with the similarity gain function) and OSLOM achieve the best performance overall at
correctly predicting the number of alliances.
(Since this serves a prediction error measurement, lower is better.)
Fig. 10: Number of predicted communities vs. time for
the Travian (Trades) dataset. LabelRankT's (red) pre-
dicted number of communities varies drastically be-
tween time steps, whereas all other algorithms make
more consistent predictions.
leverage this information. For instance, MMOG game
alliances often have a leadership council that is publicly
known. To handle this problem, we developed a variant
(D-GTG: D-GT with passing Ground Truth). Fig. 11
shows the performance improvements from increasing
the size of the seed groups from 0{20% of the total
number of agents for the Travian (Messages) dataset,
and Fig. 12 shows the performance increase for Tra-
vian (Trades). Note that extracting community mem-
bership information from the network structure of Tra-
vian (Trades) is a dicult problem because only 30%
of the edges in Travian (Trades) occur between players
within the same alliance (community). Also the dataset
has a high number of isolated nodes; about 50% of the
nodes do not belong to any alliance.
Table 5 shows the running time of all algorithms
on our largest datasets, the AS-Internet dataset (with
Fig. 11: D-GTG NMI vs. seed group size on Travian
(Messages)
Fig. 12: D-GTG NMI vs. seed group size on Travian
(Trades)
the highest number of snapshots) and hep-ph (with the
highest number of nodes). Overall, the running times
provided by all algorithms were quite reasonable, as
there are 733 snapshots in the Internet dataset and over
10,000 and 30,000 nodes in Oregon and hep-ph respec-
tively. InfoMap is the fastest algorithm on two datasets

Identifying Community Structures in Dynamic Networks 13
Table 5: Running time (sec) of all algorithms on the
AS-Internet, AS-Oregon, and hep-ph datasets
Algorithm Internet Oregon hep-ph
D-GT 610 45 1,140
LabelRankT 840 90 1,250
iLCD 750 80 1,000
OSLOM 590 35 900
InfoMap 240 42 620
Louvain 380 60 730
(Internet and hep-ph) and performs almost as well as
OSLOM on third one (Oregon). All of the algorithms
are suciently fast to run on large datasets.
5 Conclusion
This article analyzes the performance of our game the-
oretic community detection algorithm, D-GT, on dy-
namic social networks. These social networks are very
common in massively multiplayer online games, such as
Travian, where players self-organize into rapidly chang-
ing guilds and alliances. We show that D-GT's initial-
ization procedure in combination with the similarity
gain function is very eective at recovering the true
community structure of the network, both in terms of
predicting the number of communities and the players'
community membership vectors. It outperforms other
dynamic community detection methods including La-
belRankT, iLCD, and OSLOM. In cases where the com-
munities of a small number of players (e.g. the guild
leadership) is known D-GT can leverage the informa-
tion to improve the NMI performance. When simply
optimizing modularity, considering earlier community
membership is less important and static community de-
tection algorithms (InfoMap and Louvain) perform well
at this task, but all variants of D-GT oer competitive
performance.
One nice aspect of D-GT is that it is an easily exten-
sible framework. In future work we plan to experiment
with other utility functions, loss functions, and update
rules; for instance, Q-learning could be used as the up-
date rule for the agents instead of the community mem-
bership game. We also believe that it is feasible to re-
duce the runtime of D-GT by creating approximate ver-
sions of the gain function that can be calculated based
on local edge updates.
Acknowledgments
We would like to thank Drs. Nitin Agarwal and Rolf
T. Wigand at University of Arkansas for providing the
Travian dataset.References
D. Adjeroh and U. Kandaswamy. Game-theoretic anal-
ysis of network community structure. International
Journal of Computational Intelligence Research , 3
(4), 2007.
H. Alvari, S. Hashemi, and A. Hamzeh. Detecting
overlapping communities in social networks by game
theory and structural equivalence concept. In Ar-
ticial Intelligence and Computational Intelligence ,
pages 620{630. Springer Berlin Heidelberg, 2011.
H. Alvari, S. Hashemi, and A. Hamzeh. Discovering
overlapping communities in social networks: a novel
game-theoretic approach. AI Communications , 36
(2):161{177, 2013.
H. Alvari, A. Hajibagheri, and G. Sukthankar. Commu-
nity detection in dynamic social networks: A game-
theoretic approach. In IEEE/ACM International
Conference on Advances in Social Networks Analysis
and Mining (ASONAM) , pages 101{107, Aug 2014a.
H. Alvari, K. Lakkaraju, G. Sukthankar, and J. Whet-
zel. Predicting guild membership in massively mul-
tiplayer online games. In W. Kennedy, N. Agarwal,
and S. Yang, editors, Social Computing, Behavioral-
Cultural Modeling and Prediction , volume 8393 of
Lecture Notes in Computer Science , pages 215{222.
Springer International Publishing, 2014b.
G. Beigi, M. Jalili, H. Alvari, and G. Sukthankar. Lever-
aging community detection for accurate trust pre-
diction. In ASE International Conference on Social
Computing , June 2014.
G. Beigi, X. Hu, R. Maciejewski, and H. Liu. An
overview of sentiment analysis in social media and its
applications in disaster relief. In Sentiment Analysis
and Ontology Engineering , pages 313{340. Springer,
2016a.
G. Beigi, J. Tang, and H. Liu. Signed link analysis in
social media networks. In Tenth International AAAI
Conference on Web and Social Media , 2016b.
G. Beigi, J. Tang, S. Wang, and H. Liu. Exploiting
emotional information for trust/distrust prediction.
InProceedings of SIAM International Conference on
Data Mining . SIAM, 2016c.
V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and
E. Lefebvre. Fast unfolding of communities in large
networks. Journal of statistical mechanics: theory
and experiment , 2008(10):P10008, 2008.
R. Cazabet, F. Amblard, and C. Hanachi. Detection
of overlapping communities in dynamical social net-
works. In IEEE International Conference on Social
Computing , pages 309{314, 2010.
W. Chen, Z. Liu, X. Sun, and Y. Wang. A game-
theoretic framework to identify overlapping commu-

14 Alvari et al_
nities in social networks. Data Mining and Knowledge
Discovery , 21(2):224{240, 2010.
L. Danon, A. Diaz-Guilera, J. Duch, and A. Are-
nas. Comparing community structure identication.
Journal of Statistical Mechanics: Theory and Exper-
iment , 2005(09):P09008, 2005.
F. Folino and C. Pizzuti. An evolutionary multiobjec-
tive approach for community discovery in dynamic
networks. Knowledge and Data Engineering, IEEE
Transactions on , 26(8):1838{1852, Aug 2014.
S. Fortunato. Community detection in graphs. Physics
reports , 486(3):75{174, 2010.
S. Fortunato and M. Barthelemy. Resolution limit in
community detection. Proceedings of the National
Academy of Sciences , 104(1):36{41, 2007.
M. Girvan and M. E. J. Newman. Community struc-
ture in social and biological networks. Proceedings of
the National Academy of Sciences , 99(12):7821{7826,
2002.
A. Hajibagheri, H. Alvari, A. Hamzeh, and S. Hashemi.
Community detection in social networks using infor-
mation diusion. In IEEE/ACM International Con-
ference on Advances in Social Networks Analysis and
Mining , pages 702{703, 2012.
A. Hajibagheri, A. Hamzeh, and G. Sukthankar. Mod-
eling information diusion and community member-
ship using stochastic optimization. In IEEE/ACM
International Conference on Advances in Social Net-
works Analysis and Mining , pages 175{182, 2013.
A. Hajibagheri, K. Lakkaraju, G. Sukthankar, R. T.
Wigand, and N. Agarwal. Con
ict and communica-
tion in massively-multiplayer online games. In Social
Computing, Behavioral-Cultural Modeling, and Pre-
diction , pages 65{74. Springer International Publish-
ing, 2015.
J. Hopcroft, O. Khan, B. Kulis, and B. Selman. Track-
ing evolving communities in large linked networks.
Proceedings of the National Academy of Sciences ,
101:5249{5253, 2004.
P. Hui, E. Yoneki, S. Y. Chan, and J. Crowcroft. Dis-
tributed community detection in delay tolerant net-
works. In Proceedings of ACM/IEEE International
Workshop on Mobility in the Evolving Internet Ar-
chitecture , page 7, 2007.
A. Lancichinetti, F. Radicchi, J. J. Ramasco, S. Fortu-
nato, et al. Finding statistically signicant commu-
nities in networks. PloS One , 6(4):e18961, 2011.
E. A. Leicht and M. E. Newman. Community structure
in directed networks. Physical Review Letters , 100
(11):118703, 2008.
J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs
over time: densication laws, shrinking diameters and
possible explanations. In Proceedings of the ACMSIGKDD International Conference on Knowledge
Discovery in Data Mining , pages 177{187. ACM,
2005.
J. Leskovec, D. Huttenlocher, and J. Kleinberg. Pre-
dicting positive and negative links in online social
networks. In Proceedings of the 19th international
conference on World wide web , pages 641{650. ACM,
2010.
Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L.
Tseng. Facetnet: a framework for analyzing com-
munities and their evolutions in dynamic networks.
InProceeding of the International Conference on the
World Wide Web , pages 685{694. ACM, 2008.
D. J. MacKay. Information theory, inference and learn-
ing algorithms . Cambridge University Press, 2003.
M. E. Newman. Modularity and community structure
in networks. Proceedings of the National Academy of
Sciences , 103(23):8577{8582, June 2006.
M. E. J. Newman. Fast algorithm for detecting com-
munity structure in networks. Physical Review E , 69
(6):066133, 2004.
N. P. Nguyen, T. N. Dinh, Y. Shen, and M. T. Thai.
Dynamic social community detection and its appli-
cations. PLoS One , 9(4):e91431, 04 2014.
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazi-
rani, editors. Algorithmic Game Theory . Cambridge
University Press, 2007.
G. Palla, P. Pollner, A.-L. Barab asi, and T. Vicsek.
Social group dynamics in networks. In Adaptive Net-
works , pages 11{38. Springer Berlin Heidelberg, 2009.
U. N. Raghavan, R. Albert, and S. Kumara. Near lin-
ear time algorithm to detect community structures in
large-scale networks. Physical Review E , 76(3), 2007.
M. Rosvall and C. T. Bergstrom. Maps of random
walks on complex networks reveal community struc-
ture. Proceedings of the National Academy of Sci-
ences , 105(4):1118{1123, 2008.
V. Satuluri and S. Parthasarathy. Scalable graph clus-
tering using stochastic
ows: applications to commu-
nity discovery. In Proceedings of the ACM SIGKDD
International Conference on Knowledge Discovery
and Data Mining , pages 737{746, 2009.
J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu.
Graphscope: parameter-free mining of large time-
evolving graphs. In Proceedings of the ACM SIGKDD
International Conference on Knowledge Discovery
and Data Mining , pages 687{696, 2007.
M. Takaoli, R. Rabbany, and O. R. Za ane. Com-
munity evolution prediction in dynamic social net-
works. In IEEE/ACM International Conference on
Advances in Social Networks Analysis and Mining ,
pages 9{16, 2014.

Identifying Community Structures in Dynamic Networks 15
S. Van Dongen. A cluster algorithm for graphs. Tech-
nical Report 10, Centrum voor Wiskunde en Infor-
matica, 2000.
J. Xie and B. Szymanski. Towards linear time over-
lapping community detection in social networks.
InPacic-Asia Conference on Knowledge Discovery
and Data Mining . Springer, LNAI, 2012.
J. Xie and B. K. Szymanski. Community detection us-
ing a neighborhood strength driven label propagation
algorithm. In Network Science Workshop (NSW) ,
pages 188{195. IEEE, 2011.
J. Xie, M. Chen, and B. K. Szymanski. Label-
rankT: Incremental community detection in dynamic
networks via label propagation. arXiv preprint
arXiv:1305.2006 , 2013.
J. Yang and J. Leskovec. Modeling information diu-
sion in implicit networks. In 2010 IEEE International
Conference on Data Mining , pages 599{608. IEEE,
2010.
Y. Zhang, J. Wang, Y. Wang, and L. Zhou. Parallel
community detection on large networks with propin-
quity dynamics. In Proceedings of the ACM SIGKDD
International Conference on Knowledge Discovery
and Data Mining , pages 997{1006, New York, NY,
USA, 2009.