You will be presented with the full text of a science research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
the natural flux of people s changing social ties and interests generates a dynamic social network .
this invisible network can be observed by capturing daily or weekly snapshots of user activities on social media platforms 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 .
communities are emergent groups that are created as people form highly connected subnetworks with their families , co - workers , and friends . often communities are formed by participants with the same goals , interests , or a geographic location .
for instance , in mmogs , network 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 standard algorithms
. our method uses stochastic optimization to find the best community structure , assuming that the nodes are modeled as rational players who seek to maximize their personal utility while playing a _ community membership game _ with neighboring nodes . in this game , the active agent decides to join or leave different communities ; agents receive benefits 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 find it advantageous to modify their community membership strategy .
this article examines the performance of varying the amount of information propagated from prior snapshots .
even in dynamic networks , there are many nodes that retain the same community membership or rejoin their former communities . thus propagating information from previous snapshots
can provide more favorable initialization conditions for the stochastic optimization procedure .
much of the power of the d - gt framework ( originally introduced in @xcite ) 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 analysis of the algorithm s performance in common scenarios ; while retaining the same basic game - theoretic model , we evaluate different variations of our procedure .
first , we examine the performance of different utility functions , a similarity - based utility function  @xcite vs.  the use of a personalized modularity function  @xcite .
then we compare different initialization approaches in which the following information is propagated : 1 ) no information ( * d - gts * ) ; 2 ) the union of the community membership information over all snapshots ( * d - gt * ) ; 3 ) community membership 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 outperform the benchmarks .
our experiments were conducted on networks created from different 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 interactions in massively multiplayer online games ( travian messages , travian trades ) .
results were compared against five other methods : labelrankt , ilcd , oslom , infomap and louvain in terms of normalized mutual information ( nmi ) , modularity , and the number of detected communities .
the next section presents an over - view of related work on community detection in dynamic networks .
section  [ sec : method ] describes our problem formulation and our proposed method ( * * d**ynamic * * g**ame * * t**heoretic community detection ) . experimental results are provided in section  [ sec : results ] , before we conclude the article ( section  [ sec : conclusion ] ) .
the problem of community detection has been widely studied in the literature compared to the other research areas in the social networks  @xcite . in particular , in static networks
, community detection has appeared in multiple disciplines including sociology and computer science .
this has yielded a diverse set of approaches ranging from traditional network structure based algorithms  @xcite , optimization techniques  @xcite , label propagation  @xcite , propinquity  @xcite and information diffusion  @xcite . detecting community structure in dynamic networks , on the other hand ,
has attracted less research attention due to the complexity of the problem and dearth of good datasets .
there are some community detection algorithms originally design - ed for static networks that continue to perform well in dynamic datasets .
for instance , lancichinetti et al.s oslom ( order statistics local optimization method ) works on single snapshots but also benefits 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 significance with respect to a global null model  @xcite .
we use this method as one of our benchmarks , along with two other static community detection algorithms , louvain @xcite and infomap  @xcite .
these algorithms perform well on many static community detection problems and have the benefit of being fast to compute on a single network snapshot .
other network properties have also been used to perform dynamic community detection ; for instance hui et al .
@xcite proposed a distributed method for community 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 structure from scratch at each time step  @xcite . in this article ,
we evaluate the use of personal modularity as an alternative gain function to neighborhood similarity .
some studies have focused on studying the evolution of communities over time .
for instance , @xcite identified subsets of nodes ,  natural communities " , that were stable to small perturbations of the input data .
communities detected in later snapshots were matched to earlier snapshots using the natural community tree structure .
palla et al .
@xcite proposed an innovative method for detecting communities in dynamic networks based on the k - clique percolation technique ; in their approach , communities are defined as adjacent k - cliques , that share @xmath0 nodes .    machine learning has also been employed to model changes in community structure ; for instance , @xcite predict transitions in community structure by learning supervised machine learning classifiers .
this requires data on past transitions to train the classifiers , which limits its applicability to certain datasets . @xcite
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 )  @xcite , updates the community structure of the network based on time - stamped sets of edges .
nodes are added to communities 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 can not handle interconnected 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 @xcite is a framework for analyzing communities 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 communities which is usually unknown in practice . @xcite modeled dynamic community detection as a multi - objective optimization problem .
their approach is parameter free and uses evolutionary clustering to optimize a dual objective function .
the first objective selects for highly modular structures at the current time step , and the second minimizes the differences between community structures in the current and previous time steps .
d - gt also uses a stochastic optimization procedure , but all of the agents individually optimize their utilities based on local network information .
the markov cluster algorithm ( mcl )  @xcite identifies graph clusters by computing the probabilities of random walks through the graph ; flow simulations are performed by alternating expansion ( matrix squaring ) with inflation operations ( hadamard powers ) . due to its mathematical simplicity ,
it is popular for community detection in many domains but is slow and often overestimates the number of communities in the dataset .
regularized - mcl  @xcite is a variant of mcl that prevents overfitting by taking into account neighbor flows .
it can also be used within a multi - level framework ( multi - level regularized mcl ) to speed up computation by executing a sequence of coarsening operations on the graph before executing r - mcl .
labelrankt  @xcite , shares some similarities with the mcl techniques described above while improving upon them in several ways ; it is a label propagation approach in which the inflation operation is applied to the label distribution matrix rather than to the adjacency 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 simulate the decision - making process of the individuals creating the communities , rather than focusing on statistical correlations between labels of neighboring nodes .
we believe that exploiting game theory for dynamic community detection yields more realistic , fine - grained communities since intrinsically game theory is a good representation for expressing the behavior of individuals and strategic interactions among them  @xcite .    in previous work
, we have demonstrated the success of game - theoretic approaches in static community detection across several domains , including detecting guilds in massively multiplayer online games  @xcite and predicting trust between users on e - commerce sites @xcite .
many of these domains featured overlapping communities in static networks  @xcite ; however in this article the datasets are dynamic , but not overlapping .
d - gt makes a hard assignment at the termination of the stochastic optimization procedure by selecting the community assignment with the highest utility function . in this article
, we investigate the performance of different gain functions and initialization procedures , on a variety of evaluation metrics ( modularity , nmi , number of detected communities ) .
the strength of the d - gt framework is its versatility ; our results show that substantial performance improvements can be achieved by customizing it for the problem at hand .
first , we provide the formal definition of the problem and the notations used throughout the paper . given snapshots @xmath1 of a dynamic network and their corresponding underlying graphs @xmath2 , with @xmath3 vertices and @xmath4 edges , where t=1, ... ,m , we aim to detect community structure @xmath5 of the network .
table  [ tb : symb ] shows the symbols and definitions 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  @xcite . in this article
, we evaluate four different variants of the procedure : d - gt ( * * d**ynamic * * g**ame * * t**heoretic community detection ) , d - gtp ( * d - gt * with passing one * * p**revious snapshot ) d - gts ( * d - gt * with * * s**eparate runs ) and d - gtg ( * d - gt * with passing * * g**round truth ) .
[ tb : symb ]    .definition of symbols . [ cols="<,<",options="header " , ]     table  [ tb : runtime ] shows the running time of all algorithms on our largest datasets , the as - internet dataset ( with 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 respectively .
infomap is the fastest algorithm on two datasets ( internet and hep - ph ) and performs almost as well as oslom on third one ( oregon ) .
all of the algorithms are sufficiently fast to run on large datasets .
this article analyzes the performance of our game theoretic community detection algorithm , d - gt , on dynamic social networks .
these social networks are very common in massively multiplayer online games , such as travian , where players self - organize into rapidly changing guilds and alliances .
we show that d - gt s initialization procedure in combination with the similarity gain function is very effective 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 labelrankt , ilcd , and oslom . in cases where the communities of a small number of players ( e.g. the guild leadership )
is known d - gt can leverage the information to improve the nmi performance .
when simply optimizing modularity , considering earlier community membership is less important and static community detection algorithms ( infomap and louvain ) perform well at this task , but all variants of d - gt offer competitive performance .
one nice aspect of d - gt is that it is an easily extensible 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 update rule for the agents instead of the community membership game .
we also believe that it is feasible to reduce the runtime of d - gt by creating approximate versions of the gain function that can be calculated based on local edge updates .
we would like to thank drs .
nitin agarwal and rolf t.  wigand at university of arkansas for providing the travian dataset .
most real - world social networks are inherently dynamic , composed of communities that are constantly changing in membership . 
 to track these evolving communities , we need dynamic community detection techniques . 
 this article evaluates the performance of a set of game theoretic approaches for identifying communities in dynamic networks . 
 our method , d - gt ( * * d**ynamic * * g**ame * * t**heoretic community detection ) , models each network node as a rational agent who periodically plays a community membership game with its neighbors . during game play , 
 nodes seek to maximize their local utility by joining or leaving the communities of network neighbors . 
 the community structure emerges after the game reaches a nash equilibrium . 
 compared to the benchmark community detection methods , d - gt more accurately predicts the number of communities and finds community assignments with a higher normalized mutual information , while retaining a good modularity .    
 example.eps gsave newpath 20 20 moveto 20 220 lineto 220 220 lineto 220 20 lineto closepath 2 setlinewidth gsave .4 setgray fill grestore stroke grestore