library.bib

Automatically generated by Mendeley Desktop 1.13.4
Any changes to this file will be lost if it is regenerated by Mendeley.

BibTeX export options can be customized via Options -> BibTeX in Mendeley Desktop

@incollection{Gaumont2015,
author = {Gaumont, No\'{e} and Queyroi, Fran\c{c}ois and Magnien, Cl\'{e}mence and Latapy, Matthieu},
booktitle = {Complex Networks VI},
series = {Studies in Computational Intelligence},
title = {{Expected Nodes: a quality function for the detection of link communities}},
year = {2015}
}

@incollection{Gaumont2016,
author = {Gaumont, No\'{e} and Viard, Tiphaine and Fournier-S'niehotta, Rapha\'{e}l and
Wang, Qinna and Latapy, Matthieu},
booktitle = {Complex Networks VII},
series = {Studies in Computational Intelligence},
title = {{Analysis of the temporal and structural features of threads in a mailing-list}},
year = {2016}
}
@article{Gaumont2016d,
author = {Gaumont, No\'{e}},
journal = {Social Network Analysis and Mining in submission},
language = {en},
title = {{Finding remarkably dense sequences of contacts in link streams, to Social Network Analysis and Mining}},
year = {2016}
}


@article{Li2014d,
abstract = {Network dynamics plays an important role in analyzing the correlation between the function properties and the topological structure. In this paper, we propose a novel dynamical iteration (DI) algorithm, which incorporates the iterative process of membership vector with weighting scheme, i.e. weighting W and tightness T. These new elements can be used to adjust the link strength and the node compactness for improving the speed and accuracy of community structure detection. To estimate the optimal stop time of iteration, we utilize a new stability measure which is defined as the Markov random walk auto-covariance. We do not need to specify the number of communities in advance. It naturally supports the overlapping communities by associating each node with a membership vector describing the node's involvement in each community. Theoretical analysis and experiments show that the algorithm can uncover communities effectively and efficiently.},
author = {Li, Ju and Yu, Kai and Hu, Ke},
doi = {10.1142/S0129183115500916},
issn = {0129-1831},
journal = {International Journal of Modern Physics C},
keywords = {Community structure,dynamical iteration,stability optimization,tightness,weighting scheme},
language = {en},
month = nov,
pages = {1550091},
publisher = {World Scientific Publishing Company},
title = {{A novel dynamical community detection algorithm based on weighting scheme}},
url = {http://www.worldscientific.com/doi/abs/10.1142/S0129183115500916},
year = {2014}
}
@inproceedings{Coscia2012c,
address = {New York, New York, USA},
author = {Coscia, Michele and Rossetti, Giulio and Giannotti, Fosca and Pedreschi, Dino},
booktitle = {Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '12},
doi = {10.1145/2339530.2339630},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Coscia et al. - 2012 - DEMON(5).pdf:pdf},
isbn = {9781450314626},
keywords = {community discovery,complex networks,data mining},
month = aug,
pages = {615},
publisher = {ACM Press},
title = {{DEMON}},
url = {http://dl.acm.org/citation.cfm?id=2339530.2339630},
year = {2012}
}
@article{Karsai2012,
abstract = {We investigate the communication sequences of millions of people through two different channels and analyse the fine grained temporal structure of correlated event trains induced by single individuals. By focusing on correlations between the heterogeneous dynamics and the topology of egocentric networks we find that the bursty trains usually evolve for pairs of individuals rather than for the ego and his/her several neighbours, thus burstiness is a property of the links rather than of the nodes. We compare the directional balance of calls and short messages within bursty trains to the average on the actual link and show that for the trains of voice calls the imbalance is significantly enhanced, while for short messages the balance within the trains increases. These effects can be partly traced back to the technological constraints (for short messages) and partly to the human behavioural features (voice calls). We define a model that is able to reproduce the empirical results and may help us to understand better the mechanisms driving technology mediated human communication dynamics.},
author = {Karsai, M\'{a}rton and Kaski, Kimmo and Kert\'{e}sz, J\'{a}nos},
doi = {10.1371/journal.pone.0040612},
editor = {Lambiotte, Renaud},
issn = {1932-6203},
journal = {PloS one},
keywords = {Algorithms,Communication,Humans,Models, Theoretical},
month = jan,
number = {7},
pages = {e40612},
pmid = {22866176},
publisher = {Public Library of Science},
title = {{Correlated dynamics in egocentric communication networks.}},
url = {http://dx.plos.org/10.1371/journal.pone.0040612},
volume = {7},
year = {2012}
}
@inproceedings{Cafieri2014,
abstract = {We propose mathematical programming based aproaches to refine graph clustering solutions computed by heuristics. Clustering partitions are refined by applying cluster splitting and a combination of merging and splitting actions. A refinement scheme based on iteratively fixing and releasing integer variables of a mixed-integer quadratic optimization formulation appears to be particularly efficient. Computational experiments show the effectiveness and efficiency of the proposed approaches.},
author = {Cafieri, Sonia and Hansen, Pierre},
booktitle = {NA 2004, 3rd International Conference on Network Analysis},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Cafieri, Hansen - 2014 - Using mathematical programming to refine heuristic solutions for network clustering(3).pdf:pdf},
title = {{Using mathematical programming to refine heuristic solutions for network clustering}},
url = {http://hal-enac.archives-ouvertes.fr/hal-01018034},
year = {2014}
}
@article{Kim2014b,
abstract = {Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called GREEDY and STEINERSWAP that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem.},
author = {Kim, S.-Y. and Choi, D.-W. and Chung, C.-W.},
doi = {10.1093/comjnl/bxu092},
issn = {0010-4620},
journal = {The Computer Journal},
keywords = {negative weight},
mendeley-tags = {negative weight},
month = sep,
pages = {bxu092--},
title = {{Finding a Friendly Community in Social Networks Considering Bad Relationships}},
url = {http://comjnl.oxfordjournals.org/content/early/2014/09/26/comjnl.bxu092.abstract},
year = {2014}
}
@misc{Cho2014,
author = {Cho, Yoon Sik},
booktitle = {Handbook on Mixed Membership Models},
file = {:home/gaumont/Documents/Ch24\_MMM2014.pdf:pdf},
title = {{Mixed membership blockmodels for dynamic networks with feedback}},
year = {2014}
}
@article{Newman2004,
abstract = {We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.},
archivePrefix = {arXiv},
arxivId = {cond-mat/0308217},
author = {Newman, M. E J and Girvan, M.},
doi = {10.1103/PhysRevE.69.026113},
eprint = {0308217},
isbn = {1539-3755 (Print)$\backslash$r1539-3755 (Linking)},
issn = {1063651X},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
pmid = {14995526},
primaryClass = {cond-mat},
title = {{Finding and evaluating community structure in networks}},
volume = {69},
year = {2004}
}
@article{Gallotti2015,
author = {Gallotti, Riccardo and Barthelemy, Marc},
doi = {10.1038/sdata.2014.56},
issn = {2052-4463},
journal = {Scientific Data},
keywords = {Civil engineering,Complex networks,Geography,Information technology,dataset},
language = {en},
mendeley-tags = {dataset},
month = jan,
pages = {140056},
publisher = {Nature Publishing Group},
title = {{The multilayer temporal network of public transport in Great Britain}},
url = {http://www.nature.com/articles/sdata201456},
volume = {2},
year = {2015}
}
@article{Palla2005,
abstract = {Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.},
author = {Palla, Gergely and Der\'{e}nyi, Imre and Farkas, Ill\'{e}s and Vicsek, Tam\'{a}s},
doi = {10.1038/nature03607},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Palla et al. - 2005 - Uncovering the overlapping community structure of complex networks in nature and society(4).pdf:pdf},
issn = {0028-0836},
journal = {Nature},
keywords = {k-clique percolation,overlapping,printed},
language = {en},
mendeley-tags = {k-clique percolation,overlapping,printed},
month = jun,
number = {7043},
pages = {814--818},
title = {{Uncovering the overlapping community structure of complex networks in nature and society}},
url = {http://www.nature.com/nature/journal/v435/n7043/full/nature03607.html http://www.nature.com/nature/journal/v435/n7043/pdf/nature03607.pdf},
volume = {435},
year = {2005}
}
@incollection{Stabeler2012,
abstract = {Previous work has demonstrated that community-finding algorithms can provide useful information for routing algorithms in delay tolerant networks. In this work we investigate which community finding algorithm most effectively informs this routing task. While early community finding algorithms partitioned networks into flat disjoint communities, more recent methods return community structures that can be overlapping and hierarchical. Given this diversity, it seems reasonable to expect that some methods will be better suited to message routing than others. In this paper, we evaluate a number of community finding strategies and find that Link Clustering, which returns overlapping hierarchical clusters, is very effective. We also find that InfoMap performs well – this is somewhat surprising given that InfoMap returns a flat partition of the network, however this may be because the optimization that drives InfoMap is based on flow.},
author = {Stabeler, Matthew and Lee, Conrad and Cunningham, P\'{a}draig},
editor = {Koucheryavy, Yevgeni and Mamatas, Lefteris and Matta, Ibrahim and Tsaoussidis, Vassilis},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Stabeler, Lee, Cunningham - 2012 - An Assessment of Community Finding Algorithms for Community-Based Message Routing in DTNs(3).pdf:pdf},
isbn = {978-3-642-30629-7, 978-3-642-30630-3},
keywords = {Community-Based Routing,Computer Communication Networks,Delay Tolerant Networking,Information Systems Applications (incl. Internet),Information Systems and Communication Service,Software Engineering,Systems and Data Security,comp,link partition},
mendeley-tags = {Community-Based Routing,Computer Communication Networks,Delay Tolerant Networking,Information Systems Applications (incl. Internet),Information Systems and Communication Service,Software Engineering,Systems and Data Security,comp,link partition},
month = jan,
pages = {244--256},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{An Assessment of Community Finding Algorithms for Community-Based Message Routing in DTNs}},
url = {http://link.springer.com/chapter/10.1007/978-3-642-30630-3\_21 http://link.springer.com/content/pdf/10.1007/978-3-642-30630-3\_21.pdf},
year = {2012}
}
@article{Li2014b,
abstract = {In this paper, a unique algorithm is proposed to detect overlapping communities in the un-weighted and weighted networks with considerable accuracy. The maximal cliques, overlapping vertex, bridge vertex and isolated vertex are introduced. First, all the maximal cliques are extracted by the algorithm based on the deep and bread searching. Then two maximal cliques can be merged into a larger sub-graph by some given rules. In addition, the proposed algorithm successfully finds overlapping vertices and bridge vertices between communities. Experimental results using some real-world networks data show that the performance of the proposed algorithm is satisfactory.},
author = {Li, Junqiu and Wang, Xingyuan and Cui, Yaozu},
doi = {10.1016/j.physa.2014.08.025},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Li, Wang, Cui - 2014 - Uncovering the overlapping community structure of complex networks by maximal cliques.pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Complex networks,Maximal cliques,Overlapping communities},
month = aug,
title = {{Uncovering the overlapping community structure of complex networks by maximal cliques}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437114007031},
year = {2014}
}
@article{Xie2013,
author = {Xie, Jierui and Kelley, Stephen and Szymanski, Boleslaw K.},
doi = {10.1145/2501654.2501657},
file = {:home/gaumont/Documents/a43-xie.pdf:pdf},
issn = {03600300},
journal = {ACM Computing Surveys},
keywords = {Overlapping community detection,social networks},
month = aug,
number = {4},
pages = {1--35},
publisher = {ACM},
title = {{Overlapping community detection in networks}},
url = {http://dl.acm.org/citation.cfm?id=2501654.2501657},
volume = {45},
year = {2013}
}
@article{Zhang2007,
abstract = {Identification of (overlapping) communities/clusters in a complex network is a general problem in data mining of network data sets. In this paper, we devise a novel algorithm to identify overlapping communities in complex networks by the combination of a new modularity function based on generalizing NG's Q function, an approximation mapping of network nodes into Euclidean space and fuzzy c-means clustering. Experimental results indicate that the new algorithm is efficient at detecting both good clusterings and the appropriate number of clusters.},
author = {Zhang, Shihua and Wang, Rui-Sheng and Zhang, Xiang-Sun},
doi = {10.1016/j.physa.2006.07.023},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Zhang, Wang, Zhang - 2007 - Identification of overlapping community structure in complex networks using fuzzy -means clustering(3).pdf:pdf},
issn = {0378-4371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Complex network,Fuzzy   c  -means clustering,Modular function,Overlapping community structure,Spectral mapping,overlapping},
mendeley-tags = {Complex network,Fuzzy   c  -means clustering,Modular function,Overlapping community structure,Spectral mapping,overlapping},
month = jan,
number = {1},
pages = {483--490},
title = {{Identification of overlapping community structure in complex networks using fuzzy -means clustering}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437106008119 http://www.sciencedirect.com/science/article/pii/S0378437106008119/pdfft?md5=1fff03829d2d4363b94dfdb57440a7c7\&pid=1-s2.0-S0378437106008119-main.pdf},
volume = {374},
year = {2007}
}
@article{Mankad2013,
abstract = {Time series of graphs are increasingly prevalent in modern data and pose unique challenges to visual exploration and pattern extraction. This paper describes the development and application of matrix factorizations for exploration and time-varying community detection in time-evolving graph sequences. The matrix factorization model allows the user to home in on and display interesting, underlying structure and its evolution over time. The methods are scalable to weighted networks with a large number of time points or nodes, and can accommodate sudden changes to graph topology. Our techniques are demonstrated with several dynamic graph series from both synthetic and real world data, including citation and trade networks. These examples illustrate how users can steer the techniques and combine them with existing methods to discover and display meaningful patterns in sizable graphs over many time points.},
archivePrefix = {arXiv},
arxivId = {1305.7169},
author = {Mankad, Shawn and Michailidis, George},
eprint = {1305.7169},
journal = {arXiv preprint},
title = {{Structural and functional discovery in dynamic networks with non-negative matrix factorization}},
url = {http://arxiv.org/abs/1305.7169},
year = {2013}
}
@book{Queyroi2013,
abstract = {L'analyse de r\'{e}seaux (repr\'{e}sent\'{e}s par des graphes) est une composante importante dans la compr\'{e}hension de syst\`{e}mes complexes issus de nombreuses disciplines telles que la biologie, la g\'{e}ographie ou la sociologie. Nous nous int\'{e}ressons dans cette th\`{e}se aux d\'{e}compositions de ces r\'{e}seaux. Ces d\'{e}compositions sont utiles pour la compression des donn\'{e}es, la d\'{e}tection de communaut\'{e}s ou la visualisation de graphes. Une d\'{e}composition possible est un partitionnement hi\'{e}rarchique des  sommets du graphe. Nous traitons de l'\'{e}valuation de la qualit\'{e} de telles structures (leur capacit\'{e} \`{a} bien capturer la topologie du graphe) par le biais de mesures de qualit\'{e}. Nous discutons ensuite l'utilisation de ces mesures en tant que fonctions objectives \`{a} maximiser dans le cadre d'algorithmes de partitionnement. Enfin, nous nous int\'{e}ressons \`{a} la d\'{e}finition de m\'{e}taphores visuelles efficaces permettant de repr\'{e}senter diff\'{e}rentes d\'{e}compositions de graphes.},
author = {Queyroi, Fran\c{c}ois},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Queyroi - 2013 - Partitionnement de grands graphes mesures, algorithmes et visualisation.html:html},
keywords = {Community detection Partitioning Graph visualizati,D\'{e}tection de communaut\'{e}s Partitionnement Visualisa},
mendeley-tags = {Community detection Partitioning Graph visualizati,D\'{e}tection de communaut\'{e}s Partitionnement Visualisa},
month = oct,
publisher = {Bordeaux 1},
shorttitle = {Partitionnement de grands graphes},
title = {{Partitionnement de grands graphes : mesures, algorithmes et visualisation}},
url = {http://www.theses.fr/2013BOR14863},
year = {2013}
}
@article{Zhou2014,
abstract = {Community structure can naturally emerge in paths to synchronization, and scratching it from the paths is a tough issue that accounts for the diverse dynamics of synchronization. In this paper, with assumption that the synchronization on complex networks is made up of local and collective processes, we proposed a scheme to lock the local synchronization (phase locking) at a stable state meanwhile suppress the collective synchronization based on Kuramoto model. Through this scheme, the network dynamics only contains the local synchronization, which suggests that the nodes in the same community synchronize together and these synchronization clusters well reveal the community structure of network. Furthermore, by analyzing the paths to synchronization, the relations or overlaps among different communities are also obtained. Thus, the community detection based on the scheme is performed on five real networks and the observed community structures are much more apparent than modularity-based fast algorithm. Our results not only provide a deep insight to understand the synchronization dynamics on complex network but also enlarge the research scope of community detection.},
archivePrefix = {arXiv},
arxivId = {1408.5196},
author = {Zhou, Ming-Yang and Zhuo, Zhao and Cai, Shi-Min and Fu, Zhong-Qian},
eprint = {1408.5196},
file = {:home/gaumont/Documents/1408.5196.pdf:pdf},
month = aug,
pages = {8},
title = {{Community structure revealed by phase locking}},
url = {http://arxiv.org/abs/1408.5196},
year = {2014}
}
@article{LeThi2014,
abstract = {Automatic discovery of community structures in complex networks is a fundamental task in many disciplines, including physics, biology, and the social sciences. The most used criterion for characterizing the existence of a community structure in a network is modularity, a quantitative measure proposed by Newman and Girvan (2004). The discovery community can be formulated as the so-called modularity maximization problem that consists of finding a partition of nodes of a network with the highest modularity. In this letter, we propose a fast and scalable algorithm called DCAM, based on DC (difference of convex function) programming and DCA (DC algorithms), an innovative approach in nonconvex programming framework for solving the modularity maximization problem. The special structure of the problem considered here has been well exploited to get an inexpensive DCA scheme that requires only a matrix-vector product at each iteration. Starting with a very large number of communities, DCAM furnishes, as output results, an optimal partition together with the optimal number of communities c(*); that is, the number of communities is discovered automatically during DCAM's iterations. Numerical experiments are performed on a variety of real-world network data sets with up to 4,194,304 nodes and 30,359,198 edges. The comparative results with height reference algorithms show that the proposed approach outperforms them not only on quality and rapidity but also on scalability. Moreover, it realizes a very good trade-off between the quality of solutions and the run time.},
annote = {Introuvable},
author = {{Le Thi}, Hoai An and Nguyen, Manh Cuong and Dinh, Tao Pham},
doi = {10.1162/NECO\_a\_00673},
issn = {1530-888X},
journal = {Neural computation},
language = {en},
month = sep,
pages = {1--28},
pmid = {25248085},
publisher = {MIT Press  One Rogers St., Cambridge, MA 02142-1209 USA journals-info@mit.edu},
title = {{A DC Programming Approach for Finding Communities in Networks.}},
url = {http://www.mitpressjournals.org/doi/abs/10.1162/NECO\_a\_00673\#.VCkjWLvcjmE},
year = {2014}
}
@article{Lambiotte2008,
abstract = {Most methods proposed to uncover communities in complex networks rely on their structural properties. Here we introduce the stability of a network partition, a measure of its quality defined in terms of the statistical properties of a dynamical process taking place on the graph. The time-scale of the process acts as an intrinsic parameter that uncovers community structures at different resolutions. The stability extends and unifies standard notions for community detection: modularity and spectral partitioning can be seen as limiting cases of our dynamic measure. Similarly, recently proposed multi-resolution methods correspond to linearisations of the stability at short times. The connection between community detection and Laplacian dynamics enables us to establish dynamically motivated stability measures linked to distinct null models. We apply our method to find multi-scale partitions for different networks and show that the stability can be computed efficiently for large networks with extended versions of current algorithms.},
author = {Lambiotte, Renaud and Delvenne, J.-C. and Barahona, M.},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lambiotte, Delvenne, Barahona - 2008 - Laplacian Dynamics and Multiscale Modular Structure in Networks(4).pdf:pdf},
journal = {arXiv:0812.1770 [physics]},
keywords = {Incompris,Laplacian Dynamic,Physics - Physics and Society},
mendeley-tags = {Incompris,Laplacian Dynamic,Physics - Physics and Society},
month = dec,
title = {{Laplacian Dynamics and Multiscale Modular Structure in Networks}},
url = {http://arxiv.org/abs/0812.1770 http://www.arxiv.org/pdf/0812.1770.pdf},
year = {2008}
}
@article{Brutz2015,
abstract = {In this work we address the problem of detecting overlapping communities in social networks. Because the word "community" is an ambiguous term, it is necessary to quantify what it means to be a community within the context of a particular type of problem. Our interpretation is that this quantification must be done at a minimum of three scales. These scales are at the level of: individual nodes, individual communities, and the network as a whole. Each of these scales involves quantitative features of community structure that are not accurately represented at the other scales, but are important for defining a particular notion of community. Our work focuses on providing sensible ways to quantify what is desired at each of these scales for a notion of community applicable to social networks, and using these models to develop a community detection algorithm. Appealing features of our approach is that it naturally allows for nodes to belong to multiple communities, and is computationally efficient for large networks with low overall edge density. The scaling of the algorithm is \$O(N\~{}\backslash overline\{k\^{}2\} + \backslash overline\{N\_\{com\}\^{}2\})\$, where \$N\$ is the number of nodes in the network, \$\backslash overline\{N\_\{com\}\^{}2\}\$ is the average squared community size, and \$\backslash overline\{k\^{}2\}\$ is the expected value of a node's degree squared. Although our work focuses on developing a computationally efficient algorithm for overlapping community detection in the context of social networks, our primary contribution is developing a methodology that is highly modular and can easily be adapted to target specific notions of community.},
archivePrefix = {arXiv},
arxivId = {1501.05623},
author = {Brutz, Michael and Meyer, Francois G.},
eprint = {1501.05623},
month = jan,
title = {{A Modular Multiscale Approach to Overlapping Community Detection}},
url = {http://arxiv.org/abs/1501.05623},
year = {2015}
}
@inproceedings{Riche2014,
address = {New York, New York, USA},
annote = {Visu},
author = {Riche, Nathalie Henry and Riche, Yann and Roussel, Nicolas and Carpendale, Sheelagh and Madhyastha, Tara and Grabowski, Thomas J.},
booktitle = {Proceedings of the 26th Conference on l'Interaction Homme-Machine - IHM '14},
doi = {10.1145/2670444.2670461},
file = {:home/gaumont/Documents/p113-riche.pdf:pdf},
isbn = {9781450329354},
keywords = {dynamic networks,functional brain connectivity,information visualization,network visualization},
month = oct,
pages = {113--122},
publisher = {ACM Press},
title = {{LinkWave}},
url = {http://dl.acm.org/citation.cfm?id=2670444.2670461},
year = {2014}
}
@article{Dreier2014,
abstract = {Complex networks can be typically broken down into groups or modules. Discovering this "community structure" is an important step in studying the large-scale structure of networks. Many algorithms have been proposed for community detection and benchmarks have been created to evaluate their performance. Typically algorithms for community detection either partition the graph (non-overlapping communities) or find node covers (overlapping communities).   In this paper, we propose a particularly simple semi-supervised learning algorithm for finding out communities. In essence, given the community information of a small number of "seed nodes", the method uses random walks from the seed nodes to uncover the community information of the whole network. The algorithm runs in time \$O(k \backslash cdot m \backslash cdot \backslash log n)\$, where \$m\$ is the number of edges; \$n\$ the number of links; and \$k\$ the number of communities in the network. In sparse networks with \$m = O(n)\$ and a constant number of communities, this running time is almost linear in the size of the network. Another important feature of our algorithm is that it can be used for either non-overlapping or overlapping communities.   We test our algorithm using the LFR benchmark created by Lancichinetti, Fortunato, and Radicchi specifically for the purpose of evaluating such algorithms. Our algorithm can compete with the best of algorithms for both non-overlapping and overlapping communities as found in the comprehensive study of Lancichinetti and Fortunato.},
annote = {seed node and use of random walk (matrix)},
archivePrefix = {arXiv},
arxivId = {1412.4973},
author = {Dreier, Jan and Kuinke, Philipp and Przybylski, Rafael and Reidl, Felix and Rossmanith, Peter and Sikdar, Somnath},
eprint = {1412.4973},
month = dec,
title = {{Overlapping Communities in Social Networks}},
url = {http://arxiv.org/abs/1412.4973},
year = {2014}
}
@article{Shen2009,
abstract = {Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results.},
author = {Shen, Huawei and Cheng, Xueqi and Cai, Kai and Hu, Mao-Bin},
doi = {10.1016/j.physa.2008.12.021},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Shen et al. - 2009 - Detect overlapping and hierarchical community structure in networks(4).pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {05.10.-a,87.23.Ge,89.20.Hh,89.75.Hc,Community detection,EAGLE,Maximal clique,Modularity,Overlapping,Overlapping \& hierarchical community},
mendeley-tags = {Overlapping},
month = apr,
number = {8},
pages = {1706--1712},
title = {{Detect overlapping and hierarchical community structure in networks}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437108010376},
volume = {388},
year = {2009}
}
@article{Lancichinetti2010a,
author = {Lancichinetti, Andrea and Radicchi, Filippo and Ramasco, Jos\'{e} J.},
doi = {10.1103/PhysRevE.81.046110},
issn = {1539-3755},
journal = {Physical Review E},
month = apr,
number = {4},
pages = {046110},
title = {{Statistical significance of communities in networks}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.81.046110},
volume = {81},
year = {2010}
}
@article{Albano2006,
author = {Albano, Alice and Guillaume, Jean-loup},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Albano, Guillaume - 2006 - On the use of intrinsic time-scale for dynamic community detection and visualization in social networks(3).pdf:pdf},
title = {{On the use of intrinsic time-scale for dynamic community detection and visualization in social networks}},
year = {2006}
}
@article{Li2014c,
abstract = {Community detection has become an important methodology to understand the organization and function of various real-world networks. Label propagation algorithm (LPA) is a near linear time algorithm which is effective in finding a good community structure. However, it updates the labels of nodes asynchronously in random order to avoid label oscillations, resulting in poor performance, weak robustness and difficulty in parallelizing the update procedure for large-scale network and distributed dynamic complex networks. We propose a novel strategy named LPA-S to update the labels of nodes synchronously by the probability of each surrounding label, which is easy to be parallelized. We experimentally investigate the effectiveness of the proposed strategy by comparing with asynchronous LPA on both computer-generated networks and real-world networks. The experimental results show our LPA-S does not harm the quality of the partitioning while can be easily parallelized.},
annote = {LAP synchrone},
author = {Li, Shenghong and Lou, Hao and Jiang, Wen and Tang, Junhua},
doi = {10.1016/j.neucom.2014.04.084},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Li et al. - 2014 - Detecting Community Structure via Synchronous Label Propagation.pdf:pdf},
issn = {09252312},
journal = {Neurocomputing},
keywords = {Community detection,Community structure,Label propagation,Parallel,Synchronous},
month = nov,
title = {{Detecting Community Structure via Synchronous Label Propagation}},
url = {http://www.sciencedirect.com/science/article/pii/S0925231214013484},
year = {2014}
}
@inproceedings{Boutin2004,
abstract = {The aim of graph clustering is to define compact and well-separated clusters from a given graph. Cluster's compactness depends on datasets and clustering methods. In order to provide evaluation of graph clustering quality, many different indices have been proposed in previous work. Indices are used to compare different graph partitions but also different clustering techniques. Moreover, some clustering techniques are based on index optimization. Indices can also be added as visual tips in graph layouts. Despite the importance of the subject, little has been done to unify the field. It results that many indices can not be easily compared or interpreted. In this paper, we provide a unified and synthetic view of indices used in graph clustering area and discuss them. We also propose several enhanced measures.},
author = {Boutin, F. and Hascoet, M.},
doi = {10.1109/IV.2004.1320171},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Boutin, Hascoet - 2004 - Cluster validity indices for graph partitioning(4).html:html},
keywords = {ALIRE,Qualit\'{e},cluster validity indices,clustering methods,clustering quality,data visualisation,datasets,graph clustering,graph layouts,graph partitioning,graph theory,index optimization,pattern clustering},
mendeley-tags = {ALIRE,Qualit\'{e},cluster validity indices,clustering methods,clustering quality,data visualisation,datasets,graph clustering,graph layouts,graph partitioning,graph theory,index optimization,pattern clustering},
pages = {376--381},
title = {{Cluster validity indices for graph partitioning}},
url = {http://ieeexplore.ieee.org/xpl/login.jsp?tp=\&arnumber=1320171\&url=http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=1320171},
year = {2004}
}
@article{Kumpula2008,
abstract = {In complex network research clique percolation, introduced by Palla, Der\'{e}nyi, and Vicsek [Nature (London) 435, 814 (2005)], is a deterministic community detection method which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This method is based on sequentially inserting the constituent links to the network and simultaneously keeping track of the emerging community structure. Unlike existing algorithms, the SCP method allows for detecting k -clique communities at multiple weight thresholds in a single run, and can simultaneously produce a dendrogram representation of hierarchical community structure. In sparse weighted networks, the SCP algorithm can also be used for implementing the weighted clique percolation method recently introduced by Farkas [New J. Phys. 9, 180 (2007)]. The computational time of the SCP algorithm scales linearly with the number of k -cliques in the network. As an example, the method is applied to a product association network, revealing its nested community structure.},
archivePrefix = {arXiv},
arxivId = {0805.1449},
author = {Kumpula, Jussi M and Kivel\"{a}, Mikko and Kaski, Kimmo and Saram\"{a}ki, Jari},
doi = {10.1103/PhysRevE.78.026109},
eprint = {0805.1449},
isbn = {1539-3755 (Print)$\backslash$n1539-3755 (Linking)},
issn = {1539-3755},
journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
pages = {026109},
pmid = {18850899},
title = {{Sequential algorithm for fast clique percolation.}},
volume = {78},
year = {2008}
}
@article{Krings2012,
abstract = {Complex networks are often constructed by aggregating empirical data over time, such that a link represents the existence of interactions between the endpoint nodes and the link weight represents the intensity of such interactions within the aggregation time window. The resulting networks are then often considered static. More often than not, the aggregation time window is dictated by the availability of data, and the effects of its length on the resulting networks are rarely considered. Here, we address this question by studying the structural features of networks emerging from aggregating empirical data over different time intervals, focussing on networks derived from time-stamped, anonymized mobile telephone call records. Our results show that short aggregation intervals yield networks where strong links associated with dense clusters dominate; the seeds of such clusters or communities become already visible for intervals of around one week. The degree and weight distributions are seen to become stationary around a few days and a few weeks, respectively. An aggregation interval of around 30 days results in the stablest similar networks when consecutive windows are compared. For longer intervals, the effects of weak or random links become increasingly stronger, and the average degree of the network keeps growing even for intervals up to 180 days. The placement of the time window is also seen to affect the outcome: for short windows, different behavioural patterns play a role during weekends and weekdays, and for longer windows it is seen that networks aggregated during holiday periods are significantly different.},
author = {Krings, Gautier and Karsai, M\'{a}rton and Bernhardsson, Sebastian and Blondel, Vincent D and Saram\"{a}ki, Jari},
doi = {10.1140/epjds4},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Krings et al. - 2012 - Effects of time window size and placement on the structure of an aggregated communication network.pdf:pdf},
issn = {2193-1127},
journal = {EPJ Data Science},
language = {en},
month = may,
number = {1},
pages = {4},
publisher = {Springer},
title = {{Effects of time window size and placement on the structure of an aggregated communication network}},
url = {http://www.epjdatascience.com/content/1/1/4},
volume = {1},
year = {2012}
}
@article{Ball2011,
abstract = {A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.},
author = {Ball, Brian and Karrer, Brian and Newman, M. E. J.},
doi = {10.1103/PhysRevE.84.036103},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ball, Karrer, Newman - 2011 - Efficient and principled method for detecting communities in networks(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ball, Karrer, Newman - 2011 - Efficient and principled method for detecting communities in networks(3).html:html},
issn = {1539-3755},
journal = {Physical Review E},
keywords = {generativ model,link communitie,link community},
mendeley-tags = {generativ model,link communitie,link community},
month = sep,
number = {3},
pages = {036103},
publisher = {American Physical Society},
shorttitle = {Phys. Rev. E},
title = {{Efficient and principled method for detecting communities in networks}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.84.036103 http://pre.aps.org/abstract/PRE/v84/i3/e036103 http://pre.aps.org/pdf/PRE/v84/i3/e036103},
volume = {84},
year = {2011}
}
@article{Tang2010,
author = {Tang, J. and Scellato, S. and Musolesi, M. and Mascolo, C. and Latora, V.},
doi = {10.1103/PhysRevE.81.055101},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Tang et al. - 2010 - Small-world behavior in time-varying graphs(3).pdf:pdf},
issn = {1539-3755},
journal = {Physical Review E},
month = may,
number = {5},
pages = {055101},
title = {{Small-world behavior in time-varying graphs}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.81.055101},
volume = {81},
year = {2010}
}
@inproceedings{Moradi2012,
author = {Moradi, Farnaz and Olovsson, Tomas and Tsigas, Philippas},
editor = {Klasing, Ralf},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Moradi, Olovsson, Tsigas - 2012 - An Evaluation of Community Detection Algorithms on Large-Scale Email Traffic(3).pdf:pdf},
isbn = {978-3-642-30849-9},
keywords = {ALIRE,Community detection,Evaluation,dblp},
mendeley-tags = {ALIRE,Community detection,Evaluation,dblp},
pages = {283--294},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{An Evaluation of Community Detection Algorithms on Large-Scale Email Traffic.}},
url = {http://dblp.uni-trier.de/db/conf/wea/sea2012.html\#MoradiOT12 http://link.springer.com/content/pdf/10.1007/978-3-642-30850-5\_25.pdf},
volume = {7276},
year = {2012}
}
@article{Guedon2014,
archivePrefix = {arXiv},
arxivId = {1411.4686},
author = {Gu\'{e}don, Olivier and Vershynin, Roman},
eprint = {1411.4686},
month = nov,
title = {{Community detection in sparse networks via Grothendieck's inequality}},
url = {http://arxiv.org/abs/1411.4686},
year = {2014}
}
@article{Perez-Suarez2013,
abstract = {Clustering is a Data Mining technique, which has been widely used in many practical applications. From these applications, there are some, like social network analysis, topic detection and tracking, information retrieval, categorization of digital libraries, among others, where objects may belong to more than one cluster; however, most clustering algorithms build disjoint clusters. In this work, we introduce OClustR, a new graph-based clustering algorithm for building overlapping clusters. The proposed algorithm introduces a new graph-covering strategy and a new filtering strategy, which together allow to build overlapping clusterings more accurately than those built by previous algorithms. The experimental evaluation, conducted over several standard collections, showed that our proposed algorithm builds less clusters than those built by the previous related algorithms. Additionally, OClustR builds clusters with overlapping closer to the real overlapping in the collections than the overlapping generated by other clustering algorithms.},
author = {P\'{e}rez-Su\'{a}rez, Airel and Mart\'{\i}nez-Trinidad, Jos\'{e} F. and Carrasco-Ochoa, Jes\'{u}s A. and Medina-Pagola, Jos\'{e} E.},
doi = {10.1016/j.neucom.2013.04.025},
issn = {0925-2312},
journal = {Neurocomputing},
keywords = {Data mining,Graph-based algorithms,Overlapping clustering,overlapping,printed},
mendeley-tags = {Data mining,Graph-based algorithms,Overlapping clustering,overlapping,printed},
month = dec,
pages = {234--247},
shorttitle = {OClustR},
title = {{OClustR: A new graph-based algorithm for overlapping clustering}},
url = {http://www.sciencedirect.com/science/article/pii/S0925231213005432 http://www.sciencedirect.com/science/article/pii/S0925231213005432/pdfft?md5=1735488d2ef37ee44f10eb75ec0b075e\&pid=1-s2.0-S0925231213005432-main.pdf},
volume = {121},
year = {2013}
}
@article{Ding2014,
abstract = {The investigation of link prediction in networks is an important issue in many disciplines. The research of prediction algorithms which required short time but high accuracy is still a challenging task. Most of the existing algorithms are based on the topological information of the networks, including the local or global similarity indices. It is found that the hierarchical organization and community structure information may indeed provide insights for link prediction. In this paper, we propose a simple link prediction method, which fully explore the community structure information of the networks. Firstly, the community structure of the networks under different resolutions is extracted. Then, a simple frequency statistical model is applied to calculate how many times that a pair of nodes divided into the same community under different resolutions. Finally, the probability of the missing links is calculated. The performance of our algorithm is demonstrated by comparing with other seven well-known methods on two kinds of networks in different scales. The results indicate that our approach not only has a good performance on the accuracy, but also has a lower time complexity than any other algorithms which are based on hierarchical structure of the network.},
author = {Ding, Jingyi and Jiao, Licheng and Wu, Jianshe and Hou, Yunting and Qi, Yutao},
doi = {10.1016/j.physa.2014.09.005},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ding et al. - 2014 - Prediction of missing links based on multi-resolution community division.pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Community detection,Link prediction,Modularity density,Multi-resolution},
month = sep,
title = {{Prediction of missing links based on multi-resolution community division}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437114007638},
year = {2014}
}
@article{Trevino2014,
abstract = {We present a fast spectral algorithm for community detection in complex networks. Our method searches for the partition with the maximum value of the modularity via the interplay of several refinement steps that include both agglomeration and division. We validate the accuracy of the algorithm by applying it to several real-world benchmark networks. On all these, our algorithm performs as well or better than any other known polynomial scheme. This allows us to extensively study the modularity distribution in ensembles of Erd$\backslash$H\{o\}s-R$\backslash$'enyi networks, producing theoretical predictions for means and variances inclusive of finite-size corrections. Our work provides a way to accurately estimate the effect size of modularity, providing a \$z\$-score measure of it and enabling a more informative comparison of networks with different numbers of nodes and links.},
archivePrefix = {arXiv},
arxivId = {1412.8669},
author = {Trevi\~{n}o, Santiago and Nyberg, Amy and {Del Genio}, Charo I. and Bassler, Kevin E.},
eprint = {1412.8669},
file = {:home/gaumont/Documents/1412.8669v1.pdf:pdf},
month = dec,
pages = {23},
title = {{Fast and accurate determination of modularity and its effect size}},
url = {http://arxiv.org/abs/1412.8669},
year = {2014}
}
@article{Queyroi2013a,
author = {Queyroi, Fran\c{c}ois},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Queyroi - 2013 - Partitionnement de grands graphes Mesures , Algorithmes et Visualisation.pdf:pdf},
title = {{Partitionnement de grands graphes : Mesures , Algorithmes et Visualisation}},
year = {2013}
}
@article{Zhu2014,
archivePrefix = {arXiv},
arxivId = {1411.3675},
author = {Zhu, Linhong and Steeg, Greg Ver and Galstyan, Aram},
eprint = {1411.3675},
file = {:home/gaumont/Documents/1411.3675v1.pdf:pdf},
month = nov,
title = {{Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization}},
url = {http://arxiv.org/abs/1411.3675},
year = {2014}
}
@article{Lazar2010,
abstract = {In this paper we introduce a non-fuzzy measure which has been designed to rank the partitions of a network's nodes into overlapping communities. Such a measure can be useful for both quantifying clusters detected by various methods and during finding the overlapping community structure by optimization methods. The theoretical problem referring to the separation of overlapping modules is discussed, and an example for possible applications is given as well.},
annote = {modularity extension},
author = {L\'{a}z\'{a}r, A. and \'{A}bel, D. and Vicsek, T.},
doi = {10.1209/0295-5075/90/18001},
file = {:home/gaumont/Documents/0295-5075\_90\_1\_18001.pdf:pdf},
issn = {0295-5075},
journal = {EPL (Europhysics Letters)},
language = {en},
month = apr,
number = {1},
pages = {18001},
publisher = {IOP Publishing},
title = {{Modularity measure of networks with overlapping communities}},
url = {http://iopscience.iop.org/0295-5075/90/1/18001/fulltext/},
volume = {90},
year = {2010}
}
@article{Kim2011,
abstract = {Community structure exists in many real-world networks and has been reported being related to several functional properties of the networks. The conventional approach was partitioning nodes into communities, while some recent studies start partitioning links instead of nodes to find overlapping communities of nodes efficiently. We extended the map equation method, which was originally developed for node communities, to find link communities in networks. This method is tested on various kinds of networks and compared with the metadata of the networks, and the results show that our method can identify the overlapping role of nodes effectively. The advantage of this method is that the node community scheme and link community scheme can be compared quantitatively by measuring the unknown information left in the networks besides the community structure. It can be used to decide quantitatively whether or not the link community scheme should be used instead of the node community scheme. Furthermore, this method can be easily extended to the directed and weighted networks since it is based on the random walk.},
archivePrefix = {arXiv},
arxivId = {1105.0257},
author = {Kim, Youngdo and Jeong, Hawoong},
doi = {10.1103/PhysRevE.84.026110},
eprint = {1105.0257},
file = {:home/gaumont/Documents/1105.0257v2.pdf:pdf},
issn = {15393755},
journal = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
month = aug,
number = {2},
pages = {026110},
title = {{Map equation for link communities}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.84.026110},
volume = {84},
year = {2011}
}
@article{Granell2015,
abstract = {Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterwards the communities across layers. Alternatively, one can develop dedicated dynamic procedures, so that multiple snapshots are simultaneously taken into account while detecting communities, which allows to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario. Additionally, we perform several tests on various algorithms which show, unsurprisingly, that dynamic techniques are more suitable than static ones to describe community evolution.},
archivePrefix = {arXiv},
arxivId = {1501.05808},
author = {Granell, Clara and Darst, Richard K. and Arenas, Alex and Fortunato, Santo and G\'{o}mez, Sergio},
eprint = {1501.05808},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Granell et al. - 2015 - A benchmark model to assess community structure in evolving networks.pdf:pdf},
month = jan,
pages = {11},
title = {{A benchmark model to assess community structure in evolving networks}},
url = {http://arxiv.org/abs/1501.05808},
year = {2015}
}
@book{Boyd2004,
abstract = {We are developing a dual panel breast-dedicated PET system using LSO scintillators coupled to position sensitive avalanche photodiodes (PSAPD). The charge output is amplified and read using NOVA RENA-3 ASICs. This paper shows that the coincidence timing resolution of the RENA-3 ASIC can be improved using certain list-mode calibrations. We treat the calibration problem as a convex optimization problem and use the RENA-3s analog-based timing system to correct the measured data for time dispersion effects from correlated noise, PSAPD signal delays and varying signal amplitudes. The direct solution to the optimization problem involves a matrix inversion that grows order (n3) with the number of parameters. An iterative method using single-coordinate descent to approximate the inversion grows order (n). The inversion does not need to run to convergence, since any gains at high iteration number will be low compared to noise amplification. The system calibration method is demonstrated with measured pulser data as well as with two LSO-PSAPD detectors in electronic coincidence. After applying the algorithm, the 511keV photopeak paired coincidence time resolution from the LSO-PSAPD detectors under study improved by 57\%, from the raw value of 16.30.07 ns FWHM to 6.920.02 ns FWHM (11.520.05 ns to 4.890.02 ns for unpaired photons).},
archivePrefix = {arXiv},
arxivId = {1111.6189v1},
author = {Boyd, Stephen and Vandenberghe, Lieven},
booktitle = {Optimization Methods and Software},
chapter = {1,10,11},
doi = {10.1017/CBO9780511804441},
editor = {Press, Cambridge University},
eprint = {1111.6189v1},
isbn = {9780511804441},
issn = {10556788},
number = {3},
pages = {487--487},
pmid = {20876008},
publisher = {Cambridge University Press},
title = {{Convex Optimization}},
url = {http://www.informaworld.com/openurl?genre=article\&doi=10.1080/10556781003625177\&magic=crossref$\backslash$nhttp://ebooks.cambridge.org/ref/id/CBO9780511804441},
volume = {25},
year = {2004}
}
@article{Coscia2012a,
abstract = {Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighborhood, using a label propagation algorithm; finally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a limited time complexity, so that it can be used on web-scale real networks.},
archivePrefix = {arXiv},
arxivId = {1206.0629},
author = {Coscia, Michele and Rossetti, G},
doi = {10.1145/2339530.2339630},
eprint = {1206.0629},
isbn = {9781450314626},
journal = {\ldots discovery and data mining},
pages = {615--623},
title = {{Demon: a local-first discovery method for overlapping communities}},
url = {http://dl.acm.org/citation.cfm?id=2339630},
year = {2012}
}
@article{Mitra2012,
abstract = {Community finding algorithms for networks have recently been extended to dynamic data. Most of these recent methods aim at exhibiting community partitions from successive graph snapshots and thereafter connecting or smoothing these partitions using clever time-dependent features and sampling techniques. These approaches are nonetheless achieving longitudinal rather than dynamic community detection. We assume that communities are fundamentally defined by the repetition of interactions among a set of nodes over time. According to this definition, analyzing the data by considering successive snapshots induces a significant loss of information: we suggest that it blurs essentially dynamic phenomena - such as communities based on repeated inter-temporal interactions, nodes switching from a community to another across time, or the possibility that a community survives while its members are being integrally replaced over a longer time period. We propose a formalism which aims at tackling this issue in the context of time-directed datasets (such as citation networks), and present several illustrations of both empirical and synthetic dynamic networks. We eventually introduce intrinsically dynamic metrics to qualify temporal community structure and emphasize their possible role as an estimator of the quality of the community detection - taking into account the fact that various empirical contexts may call for distinct 'community' definitions and detection criteria. © 2011 Elsevier B.V. All rights reserved.},
archivePrefix = {arXiv},
arxivId = {1111.2018},
author = {Mitra, Bivas and Tabourier, Lionel and Roth, Camille},
doi = {10.1016/j.comnet.2011.10.024},
eprint = {1111.2018},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Mitra, Tabourier, Roth - 2012 - Intrinsically dynamic network communities(3).pdf:pdf},
issn = {13891286},
journal = {Computer Networks},
keywords = {Citation networks,Community detection,Community quality metrics,Dynamic networks},
pages = {1041--1053},
title = {{Intrinsically dynamic network communities}},
volume = {56},
year = {2012}
}
@article{Mata2014,
archivePrefix = {arXiv},
arxivId = {1411.4601},
author = {Mata, Ang\'{e}lica S. and Pastor-Satorras, Romualdo},
eprint = {1411.4601},
file = {:home/gaumont/Documents/1411.4601v1.pdf:pdf},
month = nov,
title = {{Slow relaxation dynamics and aging in random walks on activity driven temporal networks}},
url = {http://arxiv.org/abs/1411.4601},
year = {2014}
}
@inproceedings{Xu2007,
address = {New York, New York, USA},
author = {Xu, Xiaowei and Yuruk, Nurcan and Feng, Zhidan and Schweiger, Thomas A. J.},
booktitle = {Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '07},
doi = {10.1145/1281192.1281280},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Xu et al. - 2007 - SCAN(4).pdf:pdf},
isbn = {9781595936097},
keywords = {community Structure,graph partitioning,hubs,network clustering,outliers},
month = aug,
pages = {824},
publisher = {ACM Press},
title = {{SCAN}},
url = {http://dl.acm.org/citation.cfm?id=1281192.1281280},
year = {2007}
}
@misc{Rosenthal1995,
abstract = {This is an expository paper that presents various ideas related to nonasymptotic rates of convergence for Markov chains. Such rates are of great importance for stochastic algorithms that are widely used in statistics and in computer science. They also have applications to analysis of card shuffling and other areas. In this paper, we attempt to describe various mathematical techniques that have been used to bound such rates of convergence. In particular, we describe eigenvalue analysis, random walks on groups, coupling, and minorization conditions. Connections are made to modern areas of research wherever possible. Elements of linear algebra, probability theory, group theory, and measure theory are used, but efforts are made to keep the presentation elementary and accessible. Read More: http://epubs.siam.org/doi/abs/10.1137/1037083},
author = {Rosenthal, Jeffrey S.},
booktitle = {SIAM Review},
doi = {10.1137/1037083},
issn = {0036-1445},
pages = {387--405},
title = {{Convergence Rates for Markov Chains}},
volume = {37},
year = {1995}
}
@article{Barrat2013,
abstract = {The ever increasing adoption of mobile technologies and ubiquitous services allows to sense human behavior at unprecedented levels of details and scale. Wearable sensors are opening up a new window on human mobility and proximity at the finest resolution of face-to-face proximity. As a consequence, empirical data describing social and behavioral networks are acquiring a longitudinal dimension that brings forth new challenges for analysis and modeling. Here we review recent work on the representation and analysis of temporal networks of face-to-face human proximity, based on large-scale datasets collected in the context of the SocioPatterns collaboration. We show that the raw behavioral data can be studied at various levels of coarse-graining, which turn out to be complementary to one another, with each level exposing different features of the underlying system. We briefly review a generative model of temporal contact networks that reproduces some statistical observables. Then, we shift our focus from surface statistical features to dynamical processes on empirical temporal networks. We discuss how simple dynamical processes can be used as probes to expose important features of the interaction patterns, such as burstiness and causal constraints. We show that simulating dynamical processes on empirical temporal networks can unveil differences between datasets that would otherwise look statistically similar. Moreover, we argue that, due to the temporal heterogeneity of human dynamics, in order to investigate the temporal properties of spreading processes it may be necessary to abandon the notion of wall-clock time in favour of an intrinsic notion of time for each individual node, defined in terms of its activity level. We conclude highlighting several open research questions raised by the nature of the data at hand.},
author = {Barrat, Alain and Cattuto, Ciro},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Barrat, Cattuto - 2013 - Temporal networks of face-to-face human interactions(4).pdf:pdf},
journal = {arXiv:1305.3532 [physics]},
keywords = {ALIRE,Computer Science - Social and Information Networks,Physics - Physics and Society},
mendeley-tags = {ALIRE,Computer Science - Social and Information Networks,Physics - Physics and Society},
month = may,
title = {{Temporal networks of face-to-face human interactions}},
url = {http://arxiv.org/abs/1305.3532 http://www.arxiv.org/pdf/1305.3532.pdf},
year = {2013}
}
@article{Porumbel2011,
abstract = {A K -partition of a set S is a splitting of S into K non-overlapping classes that cover all elements of S . Numerous practical applications dealing with data partitioning or clustering require computing the distance between two partitions. Previous articles proved that one can compute it in polynomial time—minimum O ( | S | + K 2 ) and maximum O ( | S | + K 3 ) —using a reduction to the linear assignment problem. We propose several conditions for which the partition distance can be computed in O ( | S | ) time. In practical terms, this computation can be done in O ( | S | ) time for any two relatively resembling partitions (i.e. with distance less than | S | 5 ) except specially constructed cases. Finally, we prove that, even if there is a bounded number of classes for which the proposed conditions are not satisfied, one can still preserve the linear complexity by exploiting decomposition properties of the similarity matrix.},
author = {Porumbel, Daniel Cosmin and Hao, Jin Kao and Kuntz, Pascale},
doi = {10.1016/j.dam.2010.09.002},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Porumbel, Hao, Kuntz - 2011 - An efficient algorithm for computing the distance between close partitions(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Porumbel, Hao, Kuntz - 2011 - An efficient algorithm for computing the distance between close partitions(3).html:html},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
keywords = {ALIRE,Clustering comparison,Partition distance,Partition metric,Similarity between partitions,Similarity measure},
mendeley-tags = {ALIRE,Clustering comparison,Partition distance,Partition metric,Similarity between partitions,Similarity measure},
month = jan,
number = {1},
pages = {53--59},
title = {{An efficient algorithm for computing the distance between close partitions}},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X10003069 http://www.sciencedirect.com/science/article/pii/S0166218X10003069/pdfft?md5=6e7b6df25bcb2a80b16edef0b64c9b75\&pid=1-s2.0-S0166218X10003069-main.pdf},
volume = {159},
year = {2011}
}
@inproceedings{Leskovec2008,
address = {New York, New York, USA},
author = {Leskovec, Jure and Lang, Kevin J. and Dasgupta, Anirban and Mahoney, Michael W.},
booktitle = {Proceeding of the 17th international conference on World Wide Web - WWW '08},
doi = {10.1145/1367497.1367591},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Leskovec et al. - 2008 - Statistical properties of community structure in large social and information networks(4).pdf:pdf},
isbn = {9781605580852},
keywords = {community structure,conductance,graph partitioning,random walks,social networks},
month = apr,
pages = {695},
publisher = {ACM Press},
title = {{Statistical properties of community structure in large social and information networks}},
url = {http://dl.acm.org/citation.cfm?id=1367497.1367591},
year = {2008}
}
@article{Huang2013,
abstract = {Link Clustering (LC) is a relatively new method for detecting overlapping communities in networks. The basic principle of LC is to derive a transform matrix whose elements are composed of the link similarity of neighbor links based on the Jaccard distance calculation; then it applies hierarchical clustering to the transform matrix and uses a measure of partition density on the resulting dendrogram to determine the cut level for best community detection. However, the original link clustering method does not consider the link similarity of non-neighbor links, and the partition density tends to divide the communities into many small communities. In this paper, an Extended Link Clustering method (ELC) for overlapping community detection is proposed. The improved method employs a new link similarity, Extended Link Similarity (ELS), to produce a denser transform matrix, and uses the maximum value of EQ (an extended measure of quality of modularity) as a means to optimally cut the dendrogram for better partitioning of the original network space. Since ELS uses more link information, the resulting transform matrix provides a superior basis for clustering and analysis. Further, using the EQ value to find the best level for the hierarchical clustering dendrogram division, we obtain communities that are more sensible and reasonable than the ones obtained by the partition density evaluation. Experimentation on five real-world networks and artificially-generated networks shows that the ELC method achieves higher EQ and In-group Proportion (IGP) values. Additionally, communities are more realistic than those generated by either of the original LC method or the classical CPM method.},
author = {Huang, Lan and Wang, Guishen and Wang, Yan and Blanzieri, Enrico and Su, Chao},
doi = {10.1371/journal.pone.0066005},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Huang et al. - 2013 - Link Clustering with Extended Link Similarity and EQ Evaluation Division(4).pdf:pdf},
journal = {PLoS ONE},
keywords = {link partition,overlapping community},
mendeley-tags = {link partition,overlapping community},
month = jun,
number = {6},
pages = {e66005},
title = {{Link Clustering with Extended Link Similarity and EQ Evaluation Division}},
url = {http://dx.doi.org/10.1371/journal.pone.0066005 http://www.plosone.org/article/fetchObject.action?uri=info:doi/10.1371/journal.pone.0066005\&representation=PDF},
volume = {8},
year = {2013}
}
@article{Danon2005,
abstract = {We compare recent approaches to community structure identification in terms of sensitivity and computational cost. The recently proposed modularity measure is revisited and the performance of the methods as applied to ad hoc networks with known community structure, is compared. We find that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes. The work is intended as an introduction as well as a proposal for a standard benchmark test of community detection methods.},
archivePrefix = {arXiv},
arxivId = {cond-mat/0505245},
author = {Danon, Leon and D\'{\i}az-Guilera, Albert and Duch, Jordi and Arenas, Alex},
doi = {10.1088/1742-5468/2005/09/P09008},
eprint = {0505245},
issn = {1742-5468},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
keywords = {NMI},
mendeley-tags = {NMI},
month = sep,
number = {09},
pages = {P09008--P09008},
primaryClass = {cond-mat},
title = {{Comparing community structure identification}},
url = {http://arxiv.org/abs/cond-mat/0505245},
volume = {2005},
year = {2005}
}
@inproceedings{Whang2013,
abstract = {Community detection is an important task in network analysis. A community (also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. One of the most successful techniques for finding overlapping communities is based on local optimization and expansion of a community metric around a seed set of vertices. In this paper, we propose an efficient overlapping community detection algorithm using a seed set expansion approach. In particular, we develop new seeding strategies for a personalized PageRank scheme that optimizes the conductance community score. The key idea of our algorithm is to find good seeds, and then expand these seed sets using the personalized PageRank clustering procedure. Experimental results show that this seed set expansion approach outperforms other state-of-the-art overlapping community detection methods. We also show that our new seeding strategies are better than previous strategies, and are thus effective in finding good overlapping clusters in a graph.},
address = {New York, NY, USA},
author = {Whang, Joyce Jiyoung and Gleich, David F. and Dhillon, Inderjit S.},
doi = {10.1145/2505515.2505535},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Whang, Gleich, Dhillon - 2013 - Overlapping community detection using seed set expansion(3).pdf:pdf},
isbn = {978-1-4503-2263-8},
keywords = {clustering,community detection,overlapping,overlapping clusters,seed set expansion,seeds},
mendeley-tags = {clustering,community detection,overlapping,overlapping clusters,seed set expansion,seeds},
pages = {2099--2108},
publisher = {ACM},
series = {CIKM '13},
title = {{Overlapping community detection using seed set expansion}},
url = {http://doi.acm.org/10.1145/2505515.2505535 http://dl.acm.org/ft\_gateway.cfm?id=2505535\&type=pdf},
year = {2013}
}
@article{Kawadia2012,
abstract = {Temporal communities are the result of a consistent partitioning of nodes across multiple snapshots of an evolving network, and they provide insights into how dense clusters in a network emerge, combine, split and decay over time. To reliably detect temporal communities we need to not only find a good community partition in a given snapshot but also ensure that it bears some similarity to the partition(s) found in the previous snapshot(s), a particularly difficult task given the extreme sensitivity of community structure yielded by current methods to changes in the network structure. Here, motivated by the inertia of inter-node relationships, we present a new measure of partition distance called estrangement, and show that constraining estrangement enables one to find meaningful temporal communities at various degrees of temporal smoothness in diverse real-world datasets. Estrangement confinement thus provides a principled approach to uncovering temporal communities in evolving networks.},
archivePrefix = {arXiv},
arxivId = {1203.5126},
author = {Kawadia, Vikas and Sreenivasan, Sameet},
doi = {10.1038/srep00794},
eprint = {1203.5126},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kawadia, Sreenivasan - 2012 - Sequential detection of temporal communities by estrangement confinement(6).pdf:pdf},
issn = {2045-2322},
journal = {Scientific reports},
keywords = {Algorithms,Mathematics,Physical Phenomena,Software,Thermodynamics},
language = {en},
month = jan,
pages = {794},
pmid = {23145317},
publisher = {Nature Publishing Group},
title = {{Sequential detection of temporal communities by estrangement confinement.}},
url = {http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=3494021\&tool=pmcentrez\&rendertype=abstract http://www.nature.com/srep/2012/121109/srep00794/full/srep00794.html},
volume = {2},
year = {2012}
}
@techreport{Lancichinetti2009c,
abstract = {Uncovering the community structure exhibited by real networks is a crucial step towards an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom, Blondel et al. and Ronhovde and Nussinov, respectively, have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.},
annote = {Comment: 12 pages, 8 figures. The software to compute the values of our general normalized mutual information is available at http://santo.fortunato.googlepages.com/inthepress2},
author = {Lancichinetti, Andrea and Fortunato, Santo},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato - 2009 - Community detection algorithms a comparative analysis(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato - 2009 - Community detection algorithms a comparative analysis(3).html:html},
keywords = {Physics - Computational Physics,Physics - Physics and Society},
mendeley-tags = {Physics - Computational Physics,Physics - Physics and Society},
month = aug,
shorttitle = {Community detection algorithms},
title = {{Community detection algorithms: a comparative analysis}},
url = {http://arxiv.org/abs/0908.1062 http://www.arxiv.org/pdf/0908.1062.pdf},
year = {2009}
}
@article{Scholtes2013,
abstract = {We study the slow-down and speed-up of diffusion in temporal networks with non-Markovian contact sequences. We introduce a causality-preserving time-aggregated representation that allows to analyze temporal networks from the perspective of spectral graph theory. With this we provide an analytical explanation for the frequently observed slow-down of diffusion in empirical non-Markovian temporal networks. We derive an analytical prediction for the magnitude of this slow-down and validate our prediction against two empirical data sets. Counterintuitively, we further show that non-Markovian properties can result in a speed-up of diffusion that can be related to the spectral properties of the underlying temporal network.},
archivePrefix = {arXiv},
arxivId = {1307.4030},
author = {Scholtes, Ingo and Wider, Nicolas and Pfitzner, Rene and Garas, Antonios and Tessone, Claudio Juan and Schweitzer, Frank},
eprint = {1307.4030},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Scholtes et al. - 2013 - Slow-Down vs. Speed-Up of Diffusion in Non-Markovian Temporal Networks(3).pdf:pdf},
month = jul,
pages = {20},
title = {{Slow-Down vs. Speed-Up of Diffusion in Non-Markovian Temporal Networks}},
url = {http://arxiv.org/abs/1307.4030},
year = {2013}
}
@inproceedings{Spiliopoulou2013,
abstract = {There is much recent work on detecting and tracking change in clusters, often based on the study of the spatiotemporal properties of a cluster. For the many applications where cluster change is relevant, among them customer relation- ship management, fraud detection and marketing, it is also necessary to provide insights about the nature of cluster change: Is a cluster corresponding to a group of customers simply disappearing or are its members migrating to other clusters? Is a new emerging cluster reflecting a new target group of customers or does it rather consist of existing cus- tomers whose preferences shift? To answer such questions, we propose the framework MONIC for modeling and tracking of cluster transitions. Our cluster transition model en- compasses changes that involve more than one cluster, thus allowing for insights on cluster change in the whole clus- tering. Our transition tracking mechanism is not based on the topological properties of clusters, which are only available for some types of clustering, but on the contents of the underlying data stream. We present our first results on monitoring cluster transitions over the ACMdigital library.},
author = {Spiliopoulou, Myra and Ntoutsi, Eirini and Theodoridis, Yannis and Schult, Rene},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
doi = {10.1007/978-3-642-40994-3\_41},
isbn = {9783642409936},
issn = {03029743},
keywords = {big data,change detection,cluster monitoring,data streams,dynamic data},
pages = {622--626},
title = {{MONIC and followups on modeling and monitoring cluster transitions}},
volume = {8190 LNAI},
year = {2013}
}
@article{Cheng,
author = {Cheng, James and Wu, Huanhuan and Huang, Yuzhen and Li, Jinfeng},
file = {:home/gaumont/Documents/www2015\_submission\_298.pdf:pdf},
title = {{Reachability and Time-Based Path Queries in Temporal Graphs}}
}
@article{Li2014,
annote = {Entropy interne et externe \`{a} la communaut\'{e}},
author = {Li, Yongli and Zhang, Guijie and Feng, Yuqiang and Wu, Chong},
doi = {10.1007/s11192-014-1377-5},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Li et al. - 2014 - An entropy-based social network community detecting method and its application to scientometrics(4).pdf:pdf},
issn = {0138-9130},
journal = {Scientometrics},
month = jul,
title = {{An entropy-based social network community detecting method and its application to scientometrics}},
url = {http://link.springer.com/10.1007/s11192-014-1377-5},
year = {2014}
}
@article{Kovanen2011a,
abstract = {Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as networks of telecommunication, neural signal processing, biochemical reactions and human social interactions. We introduce the framework of temporal motifs to study the mesoscale topological-temporal structure of temporal networks in which the events of nodes do not overlap in time. Temporal motifs are classes of similar event sequences, where the similarity refers not only to topology but also to the temporal order of the events. We provide a mapping from event sequences to colored directed graphs that enables an efficient algorithm for identifying temporal motifs. We discuss some aspects of temporal motifs, including causality and null models, and present basic statistics of temporal motifs in a large mobile call network.},
archivePrefix = {arXiv},
arxivId = {1107.5646},
author = {Kovanen, Lauri and Karsai, M\'{a}rton and Kaski, Kimmo and Kert\'{e}sz, J\'{a}nos and Saram\"{a}ki, Jari},
doi = {10.1088/1742-5468/2011/11/P11005},
eprint = {1107.5646},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kovanen et al. - 2011 - Temporal motifs in time-dependent networks(3).5646v2:5646v2},
issn = {1742-5468},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
month = nov,
number = {11},
pages = {P11005},
title = {{Temporal motifs in time-dependent networks}},
url = {http://arxiv.org/abs/1107.5646},
volume = {2011},
year = {2011}
}
@article{Wu2012,
abstract = {The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments.},
author = {Wu, Zhihao and Lin, Youfang and Wan, Huaiyu and Tian, Shengfeng and Hu, Keyun},
doi = {10.1016/j.physa.2011.12.019},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Wu et al. - 2012 - Efficient overlapping community detection in huge real-world networks(3).pdf:pdf},
issn = {0378-4371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Overlapping nodes,comp,complex networks,overlapping community,overlapping community detection},
mendeley-tags = {Overlapping nodes,comp,complex networks,overlapping community,overlapping community detection},
month = apr,
number = {7},
pages = {2475--2490},
title = {{Efficient overlapping community detection in huge real-world networks}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437111009162 http://www.sciencedirect.com/science/article/pii/S0378437111009162/pdfft?md5=1fb5a35dab97a3239127d31ab743fc70\&pid=1-s2.0-S0378437111009162-main.pdf},
volume = {391},
year = {2012}
}
@article{Sun2014,
abstract = {In this paper, an incremental density-based clustering algorithm IncOrder is proposed for detecting communities in dynamic networks. It consists of two separate stages: an online stage and an offline stage. The online stage maintains the traversal sequence of a network and the offline stage extracts communities from the sequence. Based on a symmetric measure core-connectivity-similarity between pairs of adjacent nodes, the online stage builds an index structure, called core-connected chain, for dynamic networks. Since the slight change of a network has a very limited impact on its cluster chain, the chain of a dynamic network can be efficiently preserved. The offline stage extracts all possible density-based clustering results for all similarity thresholds from the chain. By maximizing a modularity function, the proposed method can automatically select the parameter of similarity threshold. Experimental results on a large number of real-world and synthetic networks show that the proposed method achieves high accuracy and efficiency.},
author = {Sun, Heli and Huang, Jianbin and Zhang, Xin and Liu, Jiao and Wang, Dong and Liu, Huailiang and Zou, Jianhua and Song, Qinbao},
doi = {10.1016/j.knosys.2014.07.015},
file = {:home/gaumont/Documents/1-s2.0-S095070511400272X-main.pdf:pdf},
issn = {09507051},
journal = {Knowledge-Based Systems},
keywords = {Community detection,Density-based clustering,Dynamic network,Incremental method,Modularity optimazition},
month = oct,
title = {{IncOrder: Incremental density-based community detection in dynamic networks}},
url = {http://www.sciencedirect.com/science/article/pii/S095070511400272X},
year = {2014}
}
@inproceedings{Papadimitriou2006,
abstract = {We introduce a method to discover optimal local patterns, which concisely describe the main trends in a time series. Our approach examines the time series at multiple time scales (i.e., window sizes) and efficiently discovers the key patterns in each. We also introduce a criterion to select the best window sizes, which most concisely capture the key oscillatory as well as aperiodic trends. Our key insight lies in learning an optimal orthonormal transform from the data itself, as opposed to using a predetermined basis or approximating function (such as piecewise constant, short-window Fourier or wavelets), which essentially restricts us to a particular family of trends. We go one step further, lifting even that limitation. Furthermore, our method lends itself to fast, incremental estimation in a streaming setting. Experimental evaluation shows that our method can capture meaningful patterns in a variety of settings. Our streaming approach requires order of magnitude less time and space, while still producing concise and informative patterns.},
address = {New York, NY, USA},
author = {Papadimitriou, Spiros and Yu, Philip},
doi = {10.1145/1142473.1142545},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Papadimitriou, Yu - 2006 - Optimal multi-scale patterns in time series streams(3).pdf:pdf},
isbn = {1-59593-434-0},
keywords = {SVD,empirical orthogonal functions,local patterns,multi-scale,singular spectrum,stream},
mendeley-tags = {SVD,empirical orthogonal functions,local patterns,multi-scale,singular spectrum,stream},
pages = {647--658},
publisher = {ACM},
series = {SIGMOD '06},
title = {{Optimal multi-scale patterns in time series streams}},
url = {http://doi.acm.org/10.1145/1142473.1142545 http://dl.acm.org/ft\_gateway.cfm?id=1142545\&type=pdf},
year = {2006}
}
@article{xu2014hierarchical,
author = {Xu, Kaikuo and Yuan, Changan and Wei, Xuzhong},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Xu, Yuan, Wei - 2014 - The Hierarchical Structure and Bridging Member of k-Clique Community(4).pdf:pdf},
title = {{The Hierarchical Structure and Bridging Member of k-Clique Community}},
year = {2014}
}
@article{Viard2015,
abstract = {A link stream is a sequence of triplets (t, u, v) indicating that an interaction occurred between u and v at time t. We generalize the classical notion of cliques in graphs to such link streams: for a given \^{a}ˆ†, a \^{a}ˆ†-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least every \^{a}ˆ† during this time interval. We propose an algorithm to enumerate all maximal cliques of a link stream, and illustrate its practical relevance on a real-world contact trace.},
archivePrefix = {arXiv},
arxivId = {1502.00993},
author = {Viard, Jordan and Latapy, Matthieu and Magnien, Cl\'{e}mence},
eprint = {1502.00993},
month = feb,
title = {{Computing maximal cliques in link streams}},
url = {http://arxiv.org/abs/1502.00993},
year = {2015}
}
@article{Viard2014,
archivePrefix = {arXiv},
arxivId = {1406.4969},
author = {Viard, Jordan and Latapy, Matthieu},
eprint = {1406.4969},
month = jun,
title = {{Identifying roles in an IP network with temporal and structural density}},
url = {http://arxiv.org/abs/1406.4969},
year = {2014}
}
@article{Zhang2014a,
abstract = {Community detection is a fundamental problem in network analysis which is made more challenging by overlaps between communities which often occur in practice. Here we propose a general, flexible, and interpretable generative model for overlapping communities, which can be thought of as a generalization of the degree-corrected stochastic block model. We develop an efficient spectral algorithm for estimating the community memberships, which deals with the overlaps by employing the K-medians algorithm rather than the usual K-means for clustering in the spectral domain. We show that the algorithm is asymptotically consistent when networks are not too sparse and the overlaps between communities not too large. Numerical experiments on both simulated networks and many real social networks demonstrate that our method performs very well compared to a number of benchmark methods for overlapping community detection.},
annote = {spectral method},
archivePrefix = {arXiv},
arxivId = {1412.3432},
author = {Zhang, Yuan and Levina, Elizaveta and Zhu, Ji},
eprint = {1412.3432},
month = dec,
pages = {37},
title = {{Detecting Overlapping Communities in Networks with Spectral Methods}},
url = {http://arxiv.org/abs/1412.3432},
year = {2014}
}
@article{Airoldi2008,
author = {Airoldi, Edoardo and Blei, David and Fienberg, Stephen and Xing, Eric},
file = {:home/gaumont/Documents/airoldi08a.pdf:pdf},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
pages = {1981 -- 2014},
title = {{Mixed Membership Stochastic Blockmodels}},
volume = {9},
year = {2008}
}
@techreport{Panisson2011,
abstract = {We report on a data-driven investigation aimed at understanding the dynamics of message spreading in a real-world dynamical network of human proximity. We use data collected by means of a proximity-sensing network of wearable sensors that we deployed at three different social gatherings, simultaneously involving several hundred individuals. We simulate a message spreading process over the recorded proximity network, focusing on both the topological and the temporal properties. We show that by using an appropriate technique to deal with the temporal heterogeneity of proximity events, a universal statistical pattern emerges for the delivery times of messages, robust across all the data sets. Our results are useful to set constraints for generic processes of data dissemination, as well as to validate established models of human mobility and proximity that are frequently used to simulate realistic behaviors.},
annote = {Comment: A. Panisson et al., On the dynamics of human proximity for data diffusion in ad-hoc networks, Ad Hoc Netw. (2011)},
author = {Panisson, Andr\'{e} and Barrat, Alain and Cattuto, Ciro and den Broeck, Wouter Van and Ruffo, Giancarlo and Schifanella, Rossano},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Panisson et al. - 2011 - On the Dynamics of Human Proximity for Data Diffusion in Ad-Hoc Networks(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Panisson et al. - 2011 - On the Dynamics of Human Proximity for Data Diffusion in Ad-Hoc Networks(3).html:html},
keywords = {Computer Science - Human-Computer Interaction,Computer Science - Networking and Internet Archite,Computer Science - Social and Information Networks,Physics - Physics and Society},
mendeley-tags = {Computer Science - Human-Computer Interaction,Computer Science - Networking and Internet Archite,Computer Science - Social and Information Networks,Physics - Physics and Society},
month = jun,
title = {{On the Dynamics of Human Proximity for Data Diffusion in Ad-Hoc Networks}},
url = {http://arxiv.org/abs/1106.5992 http://www.arxiv.org/pdf/1106.5992.pdf},
year = {2011}
}
@article{MOLLOY1995,
abstract = {Given a sequence of nonnegative real numbers lambda(0), lambda(1),... which sum to 1, we consider random graphs having approximately hin vertices of degree i. Essentially, we show that if Sigma i(i - 2)lambda(i) > 0, then such graphs almost surely have a giant component, while if Sigma i(i - 2)lambda(i) < 0, then almost surely all components in such graphs are small. We can apply these results to G(n,p), G(n,M), and other well-known models of random graphs. There are also applications related to the chromatic number of sparse random graphs. (C) 1995 John Wiley \& Sons, Inc.},
author = {MOLLOY, M and REED, B},
doi = {10.1002/rsa.3240060204},
issn = {1098-2418},
journal = {Random Structures and Algorithms},
keywords = {configuration model},
mendeley-tags = {configuration model},
pages = {161--179},
title = {{A CRITICAL-POINT FOR RANDOM GRAPHS WITH A GIVEN DEGREE SEQUENCE}},
url = {papers2://publication/uuid/4BE5456F-A1A8-40A8-B519-A1045DAE0F34},
volume = {6},
year = {1995}
}
@article{Gaiteri2015,
abstract = {Biological functions are often realized by groups of interacting molecules or cells. Membership in these groups may overlap when molecules or cells are reused in multiple functions. Traditional clustering methods assign each component to one group. Noisy measurements are common in high-throughput biological datasets. These two limitations reduce our ability to accurately define clusters in biological datasets and to interpret their biological functions. To address these limitations, we designed an algorithm called SpeakEasy, which detects overlapping or non-overlapping communities in biological networks. Input to SpeakEasy can be physical networks, such as molecular interactions, or inferred networks, such as gene coexpression networks. The networks can be directed or undirected, and may contain negative links. SpeakEasy combines traditional bottom-up and top-down approaches to clustering, by creating competition between clusters. Nodes that oscillate between multiple clusters in this competition are classified as multi-community nodes. SpeakEasy can quickly process networks with tens of thousands of nodes, quantify the stability of each cluster and detect an optimal number of clusters without requiring user preset parameter. Clustering networks derived from gene microarrays, protein affinity, sorted cell populations, electrophysiology, functional magnetic resonance imaging of resting-state brain activity, and synthetic datasets validate the ability of SpeakEasy to facilitate biological insights. For instance, we can identify overlapping co-regulated genes sets, multi-complex proteins and robust changes to the community structure of co-active brain regions in Parkinson disease. These insights rely on a robust overlapping clustering approach that enables a more realistic interpretation of common high-throughput datasets.},
annote = {Label propagation},
archivePrefix = {arXiv},
arxivId = {1501.04709},
author = {Gaiteri, Chris and Chen, Mingming and Szymanski, Boleslaw and Kuzmin, Konstantin and Xie, Jierui and Lee, Changkyu and Blanche, Timothy and Neto, Elias Chaibub and Huang, Su-Chun and Grabowski, Thomas and Madhyastha, Tara and Komashko, Vitalina},
eprint = {1501.04709},
month = jan,
title = {{Identifying robust clusters and multi-community nodes by combining top-down and bottom-up approaches to clustering}},
url = {http://arxiv.org/abs/1501.04709},
year = {2015}
}
@article{Shi2013a,
abstract = {There is a surge of community detection study on complex network analysis in recent years, since communities often play important roles in network systems. However, many real networks have more complex overlapping community structures. This paper proposes a novel algorithm to discover overlapping communities. Different from conventional algorithms based on node clustering, the proposed algorithm is based on link clustering. Since links usually represent unique relations among nodes, the link clustering will discover groups of links that have the same characteristics. Thus nodes naturally belong to multiple communities. The algorithm applies genetic operation to cluster on links. An effective encoding schema is designed and the number of communities can be automatically determined. Experiments on both artificial networks and real networks validate the effectiveness and efficiency of the proposed algorithm.},
annote = {Compl\'{e}tement d\'{e}bile},
author = {Shi, Chuan and Cai, Yanan and Fu, Di and Dong, Yuxiao and Wu, Bin},
doi = {10.1016/j.datak.2013.05.004},
issn = {0169023X},
journal = {Data \& Knowledge Engineering},
keywords = {Community detection,Genetic algorithm,Link community,Overlapping community},
month = sep,
pages = {394--404},
title = {{A link clustering based overlapping community detection algorithm}},
url = {http://www.sciencedirect.com/science/article/pii/S0169023X13000499},
volume = {87},
year = {2013}
}
@inproceedings{Yang2013a,
abstract = {Network communities represent basic structures for understanding the organization of real-world networks. A community (also referred to as a module or a cluster) is typically thought of as a group of nodes with more connections amongst its members than between its members and the remainder of the network. Communities in networks also overlap as nodes belong to multiple clusters at once. Due to the difficulties in evaluating the detected communities and the lack of scalable algorithms, the task of overlapping community detection in large networks largely remains an open problem. In this paper we present BIGCLAM (Cluster Affiliation Model for Big Networks), an overlapping community detection method that scales to large networks of millions of nodes and edges. We build on a novel observation that overlaps between communities are densely connected. This is in sharp contrast with present community detection methods which implicitly assume that overlaps between communities are sparsely connected and thus cannot properly extract overlapping communities in networks. In this paper, we develop a model-based community detection algorithm that can detect densely overlapping, hierarchically nested as well as non-overlapping communities in massive networks. We evaluate our algorithm on 6 large social, collaboration and information networks with ground-truth community information. Experiments show state of the art performance both in terms of the quality of detected communities as well as in speed and scalability of our algorithm.},
address = {New York, NY, USA},
author = {Yang, Jaewon and Leskovec, Jure},
booktitle = {Proceedings of the sixth ACM international \ldots},
doi = {10.1145/2433396.2433471},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yang, Leskovec - 2013 - Overlapping community detection at scale(6).pdf:pdf},
isbn = {978-1-4503-1869-3},
keywords = {matrix factorization,network communities,overlapping,overlapping community detec-,overlapping community detection,tion},
mendeley-tags = {matrix factorization,network communities,overlapping,overlapping community detection},
pages = {587--596},
publisher = {ACM},
series = {WSDM '13},
shorttitle = {Overlapping Community Detection at Scale},
title = {{Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach}},
url = {http://dl.acm.org/citation.cfm?id=2433471 http://doi.acm.org/10.1145/2433396.2433471 http://dl.acm.org/ft\_gateway.cfm?id=2433471\&type=pdf},
year = {2013}
}
@article{Rosvall2011a,
abstract = {To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network--the optimal number of levels and modular partition at each level--with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.},
archivePrefix = {arXiv},
arxivId = {1010.0431},
author = {Rosvall, Martin and Bergstrom, Carl T.},
doi = {10.1371/journal.pone.0018209},
eprint = {1010.0431},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Rosvall, Bergstrom - 2011 - Multilevel compression of random walks on networks reveals hierarchical organization in large integrated (2).pdf:pdf},
issn = {19326203},
journal = {PLoS ONE},
pmid = {21494658},
title = {{Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems}},
volume = {6},
year = {2011}
}
@inproceedings{Greene2010,
abstract = {Real-world social networks from a variety of domains can naturally be modelled as dynamic graphs. However, approaches to detecting communities have largely focused on identifying communities in static graphs. Recently, researchers have begun to consider the problem of tracking the evolution of groups of users in dynamic scenarios. Here we describe a model for tracking the progress of communities over time in a dynamic network, where each community is characterised by a series of significant evolutionary events. This model is used to motivate a community-matching strategy for efficiently identifying and tracking dynamic communities. Evaluations on synthetic graphs containing embedded events demonstrate that this strategy can successfully track communities over time in volatile networks. In addition, we describe experiments exploring the dynamic communities detected in a real mobile operator network containing millions of users.},
address = {Washington, DC, USA},
author = {Greene, Derek and Doyle, Donal and Cunningham, Padraig},
doi = {10.1109/ASONAM.2010.17},
isbn = {978-0-7695-4138-9},
keywords = {ALIRE,community finding,dynamic networks,social network analysis},
mendeley-tags = {ALIRE,community finding,dynamic networks,social network analysis},
pages = {176--183},
publisher = {IEEE Computer Society},
series = {ASONAM '10},
title = {{Tracking the Evolution of Communities in Dynamic Social Networks}},
url = {http://dx.doi.org/10.1109/ASONAM.2010.17},
year = {2010}
}
@techreport{Lambiotte2013,
abstract = {We discuss how spreading processes on temporal networks are impacted by the shape of their inter-event time distributions. Through simple mathematical arguments and toy examples, we find that the key factor is the ordering in which events take place, a property that tends to be affected by the bulk of the distributions and not only by their tail, as usually considered in the literature. We show that a detailed modeling of the temporal patterns observed in complex networks can change dramatically the properties of a spreading process, such as the ergodicity of a random walk process or the persistence of an epidemic.},
annote = {Comment: 5 pages},
author = {Lambiotte, Renaud and Tabourier, Lionel and Delvenne, Jean-Charles},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lambiotte, Tabourier, Delvenne - 2013 - Burstiness and spreading on temporal networks(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lambiotte, Tabourier, Delvenne - 2013 - Burstiness and spreading on temporal networks(3).html:html},
keywords = {Computer Science - Social and Information Networks,Physics - Physics and Society,Quantitative Biology - Populations and Evolution},
mendeley-tags = {Computer Science - Social and Information Networks,Physics - Physics and Society,Quantitative Biology - Populations and Evolution},
month = may,
title = {{Burstiness and spreading on temporal networks}},
url = {http://arxiv.org/abs/1305.0543 http://www.arxiv.org/pdf/1305.0543.pdf},
year = {2013}
}
@article{Peixoto2013,
abstract = {We investigate the detectability of modules in large networks when the number of modules is not known in advance. We employ the minimum description length (MDL) principle which seeks to minimize the total amount of information required to describe the network, and avoid overfitting. According to this criterion, we obtain general bounds on the detectability of any prescribed block structure, given the number of nodes and edges in the sampled network. We also obtain that the maximum number of detectable blocks scales as \$\backslash sqrt\{N\}\$, where \$N\$ is the number of nodes in the network, for a fixed average degree \$<k>\$. We also show that the simplicity of the MDL approach yields an efficient multilevel Monte Carlo inference algorithm with a complexity of \$O(\backslash tau N\backslash log N)\$, if the number of blocks is unknown, and \$O(\backslash tau N)\$ if it is known, where \$\backslash tau\$ is the mixing time of the Markov chain. We illustrate the application of the method on a large network of actors and films with over \$10\^{}6\$ edges, and a dissortative, bipartite block structure.},
archivePrefix = {arXiv},
arxivId = {1212.4794},
author = {Peixoto, Tiago P.},
doi = {10.1103/PhysRevLett.110.148701},
eprint = {1212.4794},
issn = {00319007},
journal = {Physical Review Letters},
title = {{Parsimonious module inference in large networks}},
volume = {110},
year = {2013}
}
@book{Sanayei2015,
address = {Cham},
doi = {10.1007/978-3-319-10759-2},
editor = {Sanayei, Ali and {E. R\"{o}ssler}, Otto and Zelinka, Ivan},
isbn = {978-3-319-10758-5},
publisher = {Springer International Publishing},
series = {Emergence, Complexity and Computation},
title = {{ISCS 2014: Interdisciplinary Symposium on Complex Systems}},
url = {http://link.springer.com/10.1007/978-3-319-10759-2},
volume = {14},
year = {2015}
}
@phdthesis{Cazabet2013,
abstract = {La d\'{e}tection de communaut\'{e}s dans les r\'{e}seaux est aujourd'hui un domaine ayant donn\'{e} lieu \`{a} une abondante litt\'{e}rature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont \'{e}t\'{e} men\'{e}s sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus \'{e}labor\'{e}s. Cependant, la majorit\'{e} de ces travaux portent sur des communaut\'{e}s statiques dans des r\'{e}seaux statiques. Or, beaucoup de r\'{e}seaux de terrains sont en fait dynamiques, ils \'{e}voluent au cours du temps. L'apport principal de cette th\`{e}se est donc la conception d'un algorithme de d\'{e}tection de communaut\'{e}s dynamiques sur des r\'{e}seaux temporels. Le manuscrit est d\'{e}coup\'{e} en quatre sections : La premi\`{e}re est un \'{e}tat de l'art, o\`{u} sont pass\'{e}s en revu les m\'{e}thodes existantes pour la d\'{e}tection de communaut\'{e}, statiques, dynamiques, avec et sans recouvrement. La seconde est la pr\'{e}sentation de la solution que nous proposons : iLCD, un framework pour la d\'{e}tection de communaut\'{e}s dynamiques dans les r\'{e}seaux temporels, ainsi que deux impl\'{e}mentations de ce framework. La troisi\`{e}me partie pr\'{e}sente les travaux effectu\'{e}s pour valider iLCD sur le plan statique, c'est \`{a} dire valider que les communaut\'{e}s trouv\'{e}es sont pertinentes compar\'{e}es \`{a} d'autres algorithmes existant sur des r\'{e}seaux statiques. Pour ce faire, nous proposons des id\'{e}es originales, afin de pouvoir comparer des m\'{e}thodes sur des graphes r\'{e}els. Enfin, la derni\`{e}re partie est consacr\'{e}e \`{a} la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des donn\'{e}es suppl\'{e}mentaires : l'apparition et la disparition de communaut\'{e}s, leur \'{e}volution en continue, ainsi que des op\'{e}rations complexes, telles que la fusion ou la division de communaut\'{e}s au cours du temps. Ce sont ces aspects qui sont valid\'{e}s ici, en \'{e}tudiant en d\'{e}tail les r\'{e}sultats obtenus sur des r\'{e}seaux r\'{e}els.},
author = {Cazabet, R\'{e}my},
keywords = {D\'{e}tection de communaut\'{e}s,communaut\'{e}s dynamiques,grands graphes,grands r\'{e}seaux,r\'{e}seaux dynamiques,r\'{e}seaux sociaux web 2.0},
mendeley-tags = {D\'{e}tection de communaut\'{e}s,communaut\'{e}s dynamiques,grands graphes,grands r\'{e}seaux,r\'{e}seaux dynamiques,r\'{e}seaux sociaux web 2.0},
month = mar,
title = {{D\'{e}tection de communaut\'{e}s dynamiques dans des r\'{e}seaux temporels}},
url = {http://tel.archives-ouvertes.fr/tel-00874017 http://tel.archives-ouvertes.fr/docs/00/87/40/17/PDF/TheseIRITSeptembre4.pdf},
year = {2013}
}
@article{Fournet2014,
abstract = {Face-to-face contacts between individuals contribute to shape social networks and play an important role in determining how infectious diseases can spread within a population. It is thus important to obtain accurate and reliable descriptions of human contact patterns occurring in various day-to-day life contexts. Recent technological advances and the development of wearable sensors able to sense proximity patterns have made it possible to gather data giving access to time-varying contact networks of individuals in specific environments. Here we present and analyze two such data sets describing with high temporal resolution the contact patterns of students in a high school. We define contact matrices describing the contact patterns between students of different classes and show the importance of the class structure. We take advantage of the fact that the two data sets were collected in the same setting during several days in two successive years to perform a longitudinal analysis on two very different timescales. We show the high stability of the contact patterns across days and across years: the statistical distributions of numbers and durations of contacts are the same in different periods, and we observe a very high similarity of the contact matrices measured in different days or different years. The rate of change of the contacts of each individual from one day to the next is also similar in different years. We discuss the interest of the present analysis and data sets for various fields, including in social sciences in order to better understand and model human behavior and interactions in different contexts, and in epidemiology in order to inform models describing the spread of infectious diseases and design targeted containment strategies.},
author = {Fournet, Julie and Barrat, Alain},
doi = {10.1371/journal.pone.0107878},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Fournet, Barrat - 2014 - Contact patterns among high school students.pdf:pdf},
issn = {1932-6203},
journal = {PloS one},
month = jan,
number = {9},
pages = {e107878},
pmid = {25226026},
title = {{Contact patterns among high school students.}},
url = {http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0107878},
volume = {9},
year = {2014}
}
@article{Gonzalez-Barrios2003,
abstract = {We present a procedure for the identification of clusters in multivariate data sets, based on the comparison between the k nearest neighbors graph, Gk, and the minimal spanning tree, MST. Our key statistic is the random quantity k̃≔ the smallest k such that Gk contains the MST. Under regularity assumptions, we show that for i.i.d. data from a density on Rd with compact support having one connected component, k̃=OPr(logn), where n denotes sample size, a bound that seems to be sharp, according to simulations. This leads to a consistent test for the identification of crisp clusters. We illustrate the use of our procedure with an example.},
author = {Gonz\'{a}lez-Barrios, Jos\'{e} Marı́a and Quiroz, Adolfo J.},
doi = {10.1016/S0167-7152(02)00421-2},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gonz\'{a}lez-Barrios, Quiroz - 2003 - A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal.pdf:pdf},
issn = {01677152},
journal = {Statistics \& Probability Letters},
keywords = {Clustering,Minimal spanning tree,Nearest neighbors graph},
month = mar,
number = {1},
pages = {23--34},
title = {{A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal spanning tree}},
url = {http://www.sciencedirect.com/science/article/pii/S0167715202004212},
volume = {62},
year = {2003}
}
@inproceedings{Kempe2000,
address = {New York, NY, USA},
author = {Kempe, David and Kleinberg, Jon and Kumar, Amit},
doi = {10.1145/335305.335364},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kempe, Kleinberg, Kumar - 2000 - Connectivity and Inference Problems for Temporal Networks(4).pdf:pdf},
isbn = {1-58113-184-4},
keywords = {ALIRE},
mendeley-tags = {ALIRE},
pages = {504--513},
publisher = {ACM},
series = {STOC '00},
title = {{Connectivity and Inference Problems for Temporal Networks}},
url = {http://doi.acm.org/10.1145/335305.335364 http://dl.acm.org/ft\_gateway.cfm?id=335364\&type=pdf},
year = {2000}
}
@article{Alvari2013,
abstract = {Identifying communities in social networks has been receiving the increasing attentions recently. However, the overlapping concept has received little attentions in the literature, although it is observed in almost all social networks. In this study, we propose a framework based on the game theory and the structural equivalence concept to address the detection of overlapping communities in social networks. Specifically, we consider the underlying graph as a hypothetical social networking website and regard each vertex of this graph as an agent performing in this multiagent environment. Since each agent may belong to several communities simultaneously, we are able to find overlapping community structure of social networks. The rigorous proof of the existence of Nash equilibrium in this game is provided which shows that the method always reaches to the final solution. Experimental results on the benchmark and real world graphs show superiority of our approach over the other state-of-the-art methods.},
author = {Alvari, Hamidreza and Hashemi, Sattar and Hamzeh, Ali},
doi = {10.3233/AIC-130557},
journal = {AI Communications},
keywords = {overlapping},
mendeley-tags = {overlapping},
month = jan,
number = {2},
pages = {161--177},
shorttitle = {Discovering overlapping communities in social netw},
title = {{Discovering overlapping communities in social networks: A novel game-theoretic approach}},
url = {http://dx.doi.org/10.3233/AIC-130557},
volume = {26},
year = {2013}
}
@article{Latouche2011,
abstract = {Complex systems in nature and in society are often represented as networks, describing the rich set of interactions between objects of interest. Many deterministic and probabilistic clustering methods have been developed to analyze such structures. Given a network, almost all of them partition the vertices into disjoint clusters, according to their connection profile. However, recent studies have shown that these techniques were too restrictive and that most of the existing networks contained overlapping clusters. To tackle this issue, we present in this paper the Overlapping Stochastic Block Model. Our approach allows the vertices to belong to multiple clusters, and, to some extent, generalizes the well-known Stochastic Block Model [Nowicki and Snijders (2001)]. We show that the model is generically identifiable within classes of equivalence and we propose an approximate inference procedure, based on global and local variational techniques. Using toy data sets as well as the French Political Blogosphere network and the transcriptional network of Saccharomyces cerevisiae, we compare our work with other approaches.},
archivePrefix = {arXiv},
arxivId = {0910.2098},
author = {Latouche, Pierre and Birmel\'{e}, Etienne and Ambroise, Christophe},
doi = {10.1214/10-AOAS382},
eprint = {0910.2098},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Latouche, Birmel\'{e}, Ambroise - 2011 - Overlapping stochastic block models with application to the French political blogosphere(3).pdf:pdf},
issn = {1932-6157},
journal = {The Annals of Applied Statistics},
keywords = {benchmark},
mendeley-tags = {benchmark},
month = mar,
number = {1},
pages = {309--336},
title = {{Overlapping stochastic block models with application to the French political blogosphere}},
url = {http://arxiv.org/abs/0910.2098},
volume = {5},
year = {2011}
}
@inproceedings{Ye2011,
abstract = {Most of the existing literature which has entirely focused on clustering nodes in large-scale networks. To discover multi-scale overlapping communities quickly, we propose a highly efficient multi-resolution link community detection algorithm to detect the link communities in massive networks based on the idea of edge labeling. First, we will get the node partition of the network based on a new multi-resolution node detection algorithm. After that, we can find the link community in a linear time by the labels of nodes. Its time complexity is near linear and its space complexity is linear. The effectiveness of our algorithm is demonstrated by extensive experiments on lots of computer generated artificial graphs and real-world networks. The results show that our algorithm is very fast and highly reliable. Tests on real and artificial networks also give excellent results comparing with the newly proposed link partition algorithm.},
author = {Ye, Qi and Wu, Bin and Zhao, Zhixiong and Wang, Bai},
doi = {10.1109/ASONAM.2011.53},
keywords = {Benchmark testing,Clustering algorithms,Complexity theory,Detection algorithms,Graph Mining,Link Community,Partitioning algorithms,Peer to peer computing,clustering node,communities,community detection,complex networks,computational complexity,computer generated artificial graphs,edge labeling,graph theory,large scale network,link partition,massive networks,multiresolution link community detection algorithm,multiresolution node detection algorithm,multiscale overlapping communities,node partition,overlapping,overlapping community,real-world networks,space complexity,time complexity},
mendeley-tags = {Benchmark testing,Clustering algorithms,Complexity theory,Detection algorithms,Graph Mining,Link Community,Partitioning algorithms,Peer to peer computing,clustering node,communities,community detection,complex networks,computational complexity,computer generated artificial graphs,edge labeling,graph theory,large scale network,link partition,massive networks,multiresolution link community detection algorithm,multiresolution node detection algorithm,multiscale overlapping communities,node partition,overlapping,overlapping community,real-world networks,space complexity,time complexity},
pages = {71--78},
title = {{Detecting Link Communities in Massive Networks}},
year = {2011}
}
@article{Liu2014b,
abstract = {Almost all existing approaches for community detection only make use of the network topology information, which completely ignore the background information of the network. However, in many real world applications, we may know some prior information that could be useful in detecting the community structures. Specifically, the true community assignments of certain nodes are known in advance. In this paper, a novel semi-supervised community detection approach is proposed based on label propagation, which can utilize prior information to guide the discovery process of community structure. Our algorithm can propagate the labels from the labeled nodes to the whole network nodes. The algorithm is evaluated on several artificial and real-world networks and shows that it is highly effective in recovering communities.},
author = {Liu, Dong and Bai, Hong-Yu and Li, Hui-Jia and Wang, Wen-Jun},
isbn = {10.1142/S0217979214502087},
keywords = {Community structure,label propagation,semi-supervised},
language = {en},
month = aug,
publisher = {World Scientific Publishing Company},
title = {{Semi-supervised community detection using label propagation}},
url = {http://www.worldscientific.com/doi/abs/10.1142/S0217979214502087},
year = {2014}
}
@article{Cao2013,
abstract = {Community detection is important for understanding networks. Previous studies observed that communities are not necessarily disjoint and might overlap. It is also agreed that some outlier vertices participate in no community, and some hubs in a community might take more important roles than others. Each of these facts has been independently addressed in previous work. But there is no algorithm, to our knowledge, that can identify these three structures altogether. To overcome this limitation, we propose a novel model where vertices are measured by their centrality in communities, and define the identification of overlapping communities, hubs, and outliers as an optimization problem, calculated by nonnegative matrix factorization. We test this method on various real networks, and compare it with several competing algorithms. The experimental results not only demonstrate its ability of identifying overlapping communities, hubs, and outliers, but also validate its superior performance in terms of clustering quality.},
author = {Cao, Xiaochun and Wang, Xiao and Jin, Di and Cao, Yixin and He, Dongxiao},
doi = {10.1038/srep02993},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Cao et al. - 2013 - Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization(3).pdf:pdf},
journal = {Scientific Reports},
keywords = {Computer science,Information technology,overlapping},
language = {en},
mendeley-tags = {Computer science,Information technology,overlapping},
month = oct,
title = {{Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization}},
url = {http://www.nature.com/srep/2013/131021/srep02993/full/srep02993.html?WT.ec\_id=SREP-639-20131101 http://www.nature.com/srep/2013/131021/srep02993/pdf/srep02993.pdf},
volume = {3},
year = {2013}
}
@article{Zhou2015,
abstract = {A hierarchical gamma process infinite edge partition model is proposed to factorize the binary adjacency matrix of an unweighted undirected relational network under a Bernoulli-Poisson link. The model describes both homophily and stochastic equivalence, and is scalable to big sparse networks by focusing its computation on pairs of linked nodes. It can not only discover overlapping communities and inter-community interactions, but also predict missing edges. A simplified version omitting inter-community interactions is also provided and we reveal its interesting connections to existing models. The number of communities is automatically inferred in a nonparametric Bayesian manner, and efficient inference via Gibbs sampling is derived using novel data augmentation techniques. Experimental results on four real networks demonstrate the models' scalability and state-of-the-art performance.},
annote = {apprentissage},
archivePrefix = {arXiv},
arxivId = {1501.06218},
author = {Zhou, Mingyuan},
eprint = {1501.06218},
month = jan,
pages = {2},
title = {{Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction}},
url = {http://arxiv.org/abs/1501.06218},
year = {2015}
}
@article{Guo2014,
abstract = {Detecting evolutionary community structure in dynamic weighted networks is important for understanding the structure and functions of networks. In this paper, an algorithm which considers the historic community structure of networks is developed to detect evolutionary community structure in dynamic weighted networks. In the proposed algorithm, two measures are proposed to determine whether to add a node to a community and whether to merge two communities to form a new community. The proposed algorithm can automatically discover evolutionary community structure in weighted networks whose number of nodes and communities are changing over time and does not need to determine the number of communities in advance. The algorithm is tested using a synthetic network and two real-word complex networks. Experiment results demonstrate that the proposed algorithm can discover evolutionary community structure in dynamic weighted networks effectively.},
author = {Guo, Chonghui and Wang, Jiajia and Zhang, Zhen},
doi = {10.1016/j.physa.2014.07.004},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Guo, Wang, Zhang - 2014 - Evolutionary community structure discovery in dynamic weighted networks(4).pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Community structure,Dynamic networks,Evolution,Weighted networks},
month = jul,
title = {{Evolutionary community structure discovery in dynamic weighted networks}},
url = {http://www.sciencedirect.com/science/article/pii/S037843711400569X},
year = {2014}
}
@misc{Meyer2014,
abstract = {North Carolina Agriculture and Technical State University

This research was partially supported by the following grants: NSF No. 1137443, NSF No. 1247663, NSF No. 1238767, DoD No. W911NF-13-0130, DoD No. W911NF-14-1-0119, and the Data Science Fellowship Award by the National
Consortium for Data Science..},
author = {Meyer, Bradley},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Meyer - 2014 - A look inside the Nodes Cohesive Attribute Micro-clustering(5).pdf:pdf},
isbn = {978-1-62561-000-3},
keywords = {Community detection,entropy,graph clustering,social network analysis},
language = {en\_US},
month = jun,
publisher = {Academy of Science and Engineering (ASE), USA, ©ASE 2014},
title = {{A look inside the Nodes: Cohesive Attribute Micro-clustering}},
url = {http://ase360.org/handle/123456789/58},
year = {2014}
}
@inproceedings{Hu2010,
author = {Hu, Jun and Han, Yanni and Hu, Jie},
booktitle = {2010 Second International Conference on Computer Modeling and Simulation},
doi = {10.1109/ICCMS.2010.192},
isbn = {978-1-4244-5642-0},
keywords = {Centralized control,Complex networks,Computational modeling,Computer networks,Computer simulation,Fluid flow measurement,Length measurement,Network topology,Physics,Uncertainty,activity effect,complex networks,global ranking,local effect,modelling,network theory (graphs),node importance,node importance modeling,topological potential,topological potential model,topological properties modeling},
language = {English},
mendeley-tags = {topological potential},
month = jan,
pages = {411--415},
publisher = {IEEE},
title = {{Topological Potential: Modeling Node Importance with Activity and Local Effect in Complex Networks}},
url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=5421123},
volume = {2},
year = {2010}
}
@article{Bender1978a,
abstract = {Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: (i) each row sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled graphs.},
author = {Bender, Edward A and Canfield, E.Rodney},
doi = {10.1016/0097-3165(78)90059-6},
issn = {00973165},
journal = {Journal of Combinatorial Theory, Series A},
keywords = {configuration model},
mendeley-tags = {configuration model},
month = may,
number = {3},
pages = {296--307},
title = {{The asymptotic number of labeled graphs with given degree sequences}},
url = {http://www.sciencedirect.com/science/article/pii/0097316578900596},
volume = {24},
year = {1978}
}
@article{Networks2014,
annote = {Parler du temp de capture de chaque graphe.},
author = {Networks, Complex},
doi = {10.1093/comnet/xxx000},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Networks - 2014 - r Fo Re vi ew On Fo r R ev On ly.pdf:pdf},
title = {{r Fo Re vi ew On Fo r R ev On ly}},
year = {2014}
}
@article{Casteigts2010a,
abstract = {The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.},
author = {Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Casteigts et al. - 2010 - Time-Varying Graphs and Dynamic Networks(4).pdf:pdf},
journal = {arXiv:1012.0009 [physics]},
keywords = {ALIRE,C.2.4,Computer Science - Distributed- Parallel- and Clus,Computer Science - Networking and Internet Archite,Computer Science - Social and Information Networks,G.2.2,Physics - Physics and Society},
mendeley-tags = {ALIRE,C.2.4,Computer Science - Distributed- Parallel- and Clus,Computer Science - Networking and Internet Archite,Computer Science - Social and Information Networks,G.2.2,Physics - Physics and Society},
month = nov,
title = {{Time-Varying Graphs and Dynamic Networks}},
url = {http://arxiv.org/abs/1012.0009 http://www.arxiv.org/pdf/1012.0009.pdf},
year = {2010}
}
@article{Lancichinetti2009a,
abstract = {Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling to investigate different hierarchical levels of organization. Tests on real and artificial networks give excellent results.},
archivePrefix = {arXiv},
arxivId = {0802.1218},
author = {Lancichinetti, Andrea and Fortunato, Santo and Kert\'{e}sz, J\'{a}nos},
doi = {10.1088/1367-2630/11/3/033015},
eprint = {0802.1218},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato, Kert\'{e}sz - 2009 - Detecting the overlapping and hierarchical community structure in complex networks(4).pdf:pdf},
issn = {1367-2630},
journal = {New Journal of Physics},
keywords = {NMI,hierarchical,overlapping},
language = {en},
mendeley-tags = {NMI,hierarchical,overlapping},
month = mar,
number = {3},
pages = {33015},
title = {{Detecting the overlapping and hierarchical community structure in complex networks}},
url = {http://arxiv.org/abs/0802.1218 http://iopscience.iop.org/1367-2630/11/3/033015 http://iopscience.iop.org/1367-2630/11/3/033015/pdf/1367-2630\_11\_3\_033015.pdf},
volume = {11},
year = {2009}
}
@article{Mucha2010,
abstract = {Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows studies of community structure in a general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.},
annote = {From Duplicate 2 (Community Structure in Time-Dependent, Multiscale, and Multiplex Networks - Mucha, Peter J.; Richardson, Thomas; Macon, Kevin; Porter, Mason A.; Onnela, Jukka-Pekka)},
author = {Mucha, Peter J. and Richardson, Thomas and Macon, Kevin and Porter, Mason A. and Onnela, Jukka-Pekka},
doi = {10.1126/science.1184819},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Mucha et al. - 2010 - Community structure in time-dependent, multiscale, and multiplex networks(4).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Mucha et al. - 2010 - Community Structure in Time-Dependent, Multiscale, and Multiplex Networks(3).pdf:pdf},
issn = {0036-8075, 1095-9203},
journal = {Science},
keywords = {Algorithms,Friends,Group Processes,Humans,Incompris,Interpersonal Relations,Models,Politics,Population Groups,Theoretical,Time Factors,United States,tensor 3d,time community},
language = {en},
mendeley-tags = {Incompris,tensor 3d,time community},
month = may,
number = {5980},
pages = {876--878},
pmid = {20466926},
title = {{Community Structure in Time-Dependent, Multiscale, and Multiplex Networks}},
url = {http://www.sciencemag.org/content/328/5980/876.full http://www.sciencemag.org/content/328/5980/876 http://www.ncbi.nlm.nih.gov/pubmed/20466926 http://www.sciencemag.org/content/328/5980/876.full.pdf},
volume = {328},
year = {2010}
}
@article{Valles-Catala2014,
annote = {Recover layer though inference},
archivePrefix = {arXiv},
arxivId = {1411.1098},
author = {Valles-Catala, Toni and Massucci, Francesco A. and Guimera, Roger and Sales-Pardo, Marta},
eprint = {1411.1098},
keywords = {Stochastic},
mendeley-tags = {Stochastic},
month = nov,
title = {{Multilayer stochastic block models reveal the multilayer structure of complex networks}},
url = {http://arxiv.org/abs/1411.1098},
year = {2014}
}
@inproceedings{Wu2010a,
abstract = {Communities exist in complex networks of different areas, and in some cases they may overlap between each other. Community detection is a good way to understand the structure, function and evolution of complex networks. There have been some methods to find disjoint or overlapping communities. While most of these methods only fit one single situation, disjoint or overlapping. In our opinion, it is unreasonable to find disjoint communities on a network with clear overlap or to find overlapping communities on a network without any visible overlapping node. In this paper, we propose a link partition based method which can find communities with adjustable extent of overlapping according to backgrounds of specific applications or personal preferences. Experimental results on some real-world networks show that our method can find reasonable communities with adjustable extent of overlapping, and is suitable for networks with high densities and large scales.},
author = {Wu, Zhihao and Lin, Youfang and Wan, Huaiyu and Tian, Shengfeng},
booktitle = {Proceedings of 2010 IEEE International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2010},
doi = {10.1109/ISKE.2010.5680851},
file = {:home/gaumont/Documents/Wu2010Fast.pdf:pdf},
isbn = {9781424467907},
pages = {376--379},
title = {{A fast and reasonable method for community detection with adjustable extent of overlapping}},
year = {2010}
}
@inproceedings{Chakrabarti2006,
address = {New York, New York, USA},
author = {Chakrabarti, Deepayan and Kumar, Ravi and Tomkins, Andrew},
booktitle = {Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '06},
doi = {10.1145/1150402.1150467},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Chakrabarti, Kumar, Tomkins - 2006 - Evolutionary clustering.pdf:pdf},
isbn = {1595933395},
keywords = {agglomerative,clustering,k-means,temporal clustering,temporal evolution},
mendeley-tags = {temporal clustering},
month = aug,
pages = {554},
publisher = {ACM Press},
title = {{Evolutionary clustering}},
url = {http://dl.acm.org/citation.cfm?id=1150402.1150467},
year = {2006}
}
@article{Cazabet2013a,
abstract = {La d\'{e}tection de communaut\'{e}s dans les r\'{e}seaux est aujourd'hui un domaine ayant donn\'{e} lieu \`{a} une abondante litt\'{e}rature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont \'{e}t\'{e} men\'{e}s sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus \'{e}labor\'{e}s. Cependant, la majorit\'{e} de ces travaux portent sur des communaut\'{e}s statiques dans des r\'{e}seaux statiques. Or, beaucoup de r\'{e}seaux de terrains sont en fait dynamiques, ils \'{e}voluent au cours du temps. L'apport principal de cette th\`{e}se est donc la conception d'un algorithme de d\'{e}tection de communaut\'{e}s dynamiques sur des r\'{e}seaux temporels. Le manuscrit est d\'{e}coup\'{e} en quatre sections : La premi\`{e}re est un \'{e}tat de l'art, o\`{u} sont pass\'{e}s en revu les m\'{e}thodes existantes pour la d\'{e}tection de communaut\'{e}, statiques, dynamiques, avec et sans recouvrement. La seconde est la pr\'{e}sentation de la solution que nous proposons : iLCD, un framework pour la d\'{e}tection de communaut\'{e}s dynamiques dans les r\'{e}seaux temporels, ainsi que deux impl\'{e}mentations de ce framework. La troisi\`{e}me partie pr\'{e}sente les travaux effectu\'{e}s pour valider iLCD sur le plan statique, c'est \`{a} dire valider que les communaut\'{e}s trouv\'{e}es sont pertinentes compar\'{e}es \`{a} d'autres algorithmes existant sur des r\'{e}seaux statiques. Pour ce faire, nous proposons des id\'{e}es originales, afin de pouvoir comparer des m\'{e}thodes sur des graphes r\'{e}els. Enfin, la derni\`{e}re partie est consacr\'{e}e \`{a} la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des donn\'{e}es suppl\'{e}mentaires : l'apparition et la disparition de communaut\'{e}s, leur \'{e}volution en continue, ainsi que des op\'{e}rations complexes, telles que la fusion ou la division de communaut\'{e}s au cours du temps. Ce sont ces aspects qui sont valid\'{e}s ici, en \'{e}tudiant en d\'{e}tail les r\'{e}sultats obtenus sur des r\'{e}seaux r\'{e}els.},
author = {Cazabet, R\'{e}my},
file = {:home/gaumont/Documents/TheseIRITSeptembre4.pdf:pdf},
keywords = {D\'{e}tection de communaut\'{e}s,communaut\'{e}s dynamiques,grands graphes,grands r\'{e}seaux,r\'{e}seaux dynamiques,r\'{e}seaux sociaux web 2.0},
month = mar,
title = {{D\'{e}tection de communaut\'{e}s dynamiques dans des r\'{e}seaux temporels}},
url = {http://tel.archives-ouvertes.fr/tel-00874017},
year = {2013}
}
@misc{Chopade2014,
abstract = {Department of Computer Science, North Carolina A\&T State University, Greensboro, NC-27411, USA Our thanks to The United States Department of Defense (DoD), National Science Foundation (NSF) and National Consortium for Data Science (NCDS) for their support and finance for this project. This research was partially supported by the following grants: NSF No. 1137443, NSF No. 1247663, NSF No. 1238767, The United States Department of Defense, DoD No. W911NF-13-0130, DoD No. W911NF-14-1-0119, and the Data Science Fellowship Award by the National Consortium for Data Science.},
author = {Chopade, Pravin and Zhan, Justin},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Chopade, Zhan - 2014 - Community Detection in Large Scale Big Data Networks(3).pdf:pdf},
isbn = {http://www.ase360.org/handle/123456789/64},
keywords = {Big Data,Community,Large Scale Network,Modularity,Optimization.},
language = {en\_US},
month = jun,
publisher = {Academy of Science and Engineering (ASE), USA, ©ASE 2014},
title = {{Community Detection in Large Scale Big Data Networks}},
url = {http://ase360.org/handle/123456789/64},
year = {2014}
}
@article{Ma2014,
abstract = {Although more connections between individuals in a social network can be identified with the development of high techniques, to obtain the complete relation information between individuals is still hard due to complex structure and individual privacy. However, the social networks have communities. In our work, we aim at mining the invisible or missing relations between individuals within a community in social networks. We propose our algorithm according to the fact that the individuals exist in communities satisfying Nash equilibrium, which is borrowed from game-theoretic concepts often used in economic researches. Each hidden relation is explored through the individual's loyalty to their community. To the best of our knowledge, this is the first work that studies the problem of mining hidden links from the aspect of Nash equilibrium. Eventually we confirm our approach's superiority from extensive experiments over real-world social networks.},
author = {Ma, Huan and Lu, Zaixin and Li, Deying and Zhu, Yuqing and Fan, Lidan and Wu, Weili},
doi = {10.1016/j.tcs.2014.08.006},
file = {:home/gaumont/Documents/1-s2.0-S0304397514006136-main.pdf:pdf},
issn = {03043975},
journal = {Theoretical Computer Science},
keywords = {Approximation algorithm,Mining hidden links,Nash equilibrium,Social networks,Vertex pair proximity},
month = aug,
title = {{Mining hidden links in social networks to achieve equilibrium}},
url = {http://www.sciencedirect.com/science/article/pii/S0304397514006136},
year = {2014}
}
@article{Guimera2003,
annote = {No ground truth},
author = {Guimer\`{a}, R. and Danon, L. and D\'{\i}az-Guilera, A. and Giralt, F. and Arenas, A.},
doi = {10.1103/PhysRevE.68.065103},
issn = {1063-651X},
journal = {Physical Review E},
month = dec,
number = {6},
pages = {065103},
title = {{Self-similar community structure in a network of human interactions}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.68.065103},
volume = {68},
year = {2003}
}
@article{Hashimoto2014,
archivePrefix = {arXiv},
arxivId = {1411.5720},
author = {Hashimoto, Tatsunori B. and Sun, Yi and Jaakkola, Tommi S.},
eprint = {1411.5720},
month = nov,
title = {{Metric recovery from directed unweighted graphs}},
url = {http://arxiv.org/abs/1411.5720},
year = {2014}
}
@article{DeDomenico2014,
abstract = {Unveiling the community structure of networks is a powerful methodology to comprehend interconnected systems across the social and natural sciences. To identify different types of functional modules in interaction data aggregated in a single network layer, researchers have developed many powerful methods. For example, flow-based methods have proven useful for identifying modular dynamics in weighted and directed networks that capture constraints on flow in the systems they represent. However, many networked systems consist of agents or components that exhibit multiple layers of interactions. Inevitably, representing this intricate network of networks as a single aggregated network leads to information loss and may obscure the actual organization. Here we propose a method based on compression of network flows that can identify modular flows in non-aggregated multilayer networks. Our numerical experiments on synthetic networks show that the method can accurately identify modules that cannot be identified in aggregated networks or by analyzing the layers separately. We capitalize on our findings and reveal the community structure of two multilayer collaboration networks: scientists affiliated to the Pierre Auger Observatory and scientists publishing works on networks on the arXiv. Compared to conventional aggregated methods, the multilayer method reveals smaller modules with more overlap that better capture the actual organization.},
archivePrefix = {arXiv},
arxivId = {1408.2925},
author = {{De Domenico}, Manlio and Lancichinetti, Andrea and Arenas, Alex and Rosvall, Martin},
eprint = {1408.2925},
file = {:home/gaumont/Documents/1408.2925v1.pdf:pdf},
month = aug,
title = {{Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems}},
url = {http://arxiv.org/abs/1408.2925},
year = {2014}
}
@techreport{Kovanen2011,
abstract = {Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as networks of telecommunication, neural signal processing, biochemical reactions and human social interactions. We introduce the framework of temporal motifs to study the mesoscale topological-temporal structure of temporal networks in which the events of nodes do not overlap in time. Temporal motifs are classes of similar event sequences, where the similarity refers not only to topology but also to the temporal order of the events. We provide a mapping from event sequences to colored directed graphs that enables an efficient algorithm for identifying temporal motifs. We discuss some aspects of temporal motifs, including causality and null models, and present basic statistics of temporal motifs in a large mobile call network.},
annote = {Comment: 18 pages, 8 figures; minor revisions},
author = {Kovanen, Lauri and Karsai, M\'{a}rton and Kaski, Kimmo and Kert\'{e}sz, J\'{a}nos and Saram\"{a}ki, Jari},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kovanen et al. - 2011 - Temporal motifs in time-dependent networks(3).5646v2:5646v2;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kovanen et al. - 2011 - Temporal motifs in time-dependent networks(3).html:html},
keywords = {Computer Science - Social and Information Networks,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society},
mendeley-tags = {Computer Science - Social and Information Networks,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society},
month = jul,
title = {{Temporal motifs in time-dependent networks}},
url = {http://arxiv.org/abs/1107.5646 http://www.arxiv.org/pdf/1107.5646.pdf},
year = {2011}
}
@inproceedings{Wang2014,
annote = {Label Propagation Algo modifi\'{e}},
author = {Wang, Yi Bo and Wang, Wen Jun and Liu, Dong and Liu, Xiao and Jiao, Peng Fei},
booktitle = {Advanced Materials Research},
isbn = {978-3-03835-314-0},
issn = {1662-8985},
keywords = {LPA},
mendeley-tags = {LPA},
month = nov,
pages = {1566--1571},
title = {{Using Prior Knowledge for Community Detection by Label Propagation Algorithm}},
url = {http://www.scientific.net/AMR.1049-1050.1566},
volume = {1049-1050},
year = {2014}
}
@inproceedings{Jiang2014,
address = {New York, New York, USA},
annote = {detection de noeuds insolite},
author = {Jiang, Meng and Cui, Peng and Beutel, Alex and Faloutsos, Christos and Yang, Shiqiang},
booktitle = {Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14},
doi = {10.1145/2623330.2623632},
file = {:home/gaumont/Documents/p941-jiang.pdf:pdf},
isbn = {9781450329569},
keywords = {anomalous behavior,outlier detection,zombie follower},
month = aug,
pages = {941--950},
publisher = {ACM Press},
title = {{CatchSync}},
url = {http://dl.acm.org/citation.cfm?id=2623330.2623632},
year = {2014}
}
@article{Fortunato2010,
abstract = {The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.},
archivePrefix = {arXiv},
arxivId = {0906.0612},
author = {Fortunato, Santo},
doi = {10.1016/j.physrep.2009.11.002},
eprint = {0906.0612},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Fortunato - 2010 - Community detection in graphs(4).pdf:pdf},
isbn = {0370-1573},
issn = {0370-1573},
journal = {Physics Reports},
keywords = {Clusters,Graphs,Statistical physics,graphs},
mendeley-tags = {Clusters,Statistical physics,graphs},
month = feb,
number = {3–5},
pages = {75--174},
pmid = {22166104},
title = {{Community detection in graphs}},
url = {http://www.sciencedirect.com/science/article/pii/S0370157309002841 http://www.sciencedirect.com/science/article/pii/S0370157309002841/pdfft?md5=73579bd7359e961d3fdf5788ddd437e0\&pid=1-s2.0-S0370157309002841-main.pdf},
volume = {486},
year = {2010}
}
@article{Perez-Suarez2013a,
abstract = {Most clustering algorithms organize a collection of objects into a set of disjoint clusters. Although this approach has been successfully applied in unsupervised learning, there are several applications where objects could belong to more than one cluster. Overlapping clustering is an alternative in those contexts like social network analysis, information retrieval and bioinformatics, among other problems where non-disjoint clusters appear. In addition, there are environments where the collection changes frequently and the clustering must be updated; however, most of the existing overlapping clustering algorithms are not able to efficiently update the clustering. In this paper, we introduce a new overlapping clustering algorithm, called DClustR, which is based on the graph theory approach and it introduces a new strategy for building more accurate overlapping clusters than those built by state-of-the-art algorithms. Moreover, our algorithm introduces a new strategy for efficiently updating the clustering when the collection changes. The experimentation conducted over several standard collections shows the good performance of the proposed algorithm, wrt. accuracy and efficiency.},
author = {P\'{e}rez-Su\'{a}rez, Airel and Mart\'{\i}nez-Trinidad, Jos\'{e} Fco. and Carrasco-Ochoa, Jes\'{u}s A. and Medina-Pagola, Jos\'{e} E.},
doi = {10.1016/j.patcog.2013.03.022},
issn = {0031-3203},
journal = {Pattern Recognition},
keywords = {Data mining,Dynamic clustering algorithms,Overlapping clustering algorithms,clustering,overlapping},
mendeley-tags = {Data mining,Dynamic clustering algorithms,Overlapping clustering algorithms,clustering,overlapping},
month = nov,
number = {11},
pages = {3040--3055},
title = {{An algorithm based on density and compactness for dynamic overlapping clustering}},
url = {http://www.sciencedirect.com/science/article/pii/S0031320313001519 http://www.sciencedirect.com/science/article/pii/S0031320313001519/pdfft?md5=31dbbdf1504a4027059bdb57451f0d57\&pid=1-s2.0-S0031320313001519-main.pdf},
volume = {46},
year = {2013}
}
@article{Xiang2014,
archivePrefix = {arXiv},
arxivId = {1411.2721},
author = {Xiang, Ju and Tang, Yan-Ni and Gao, Yuan-Yuan and Zhang, Yan and Deng, Ke and Xu, Xiao-Ke and Hu, Ke},
eprint = {1411.2721},
keywords = {Biblio},
mendeley-tags = {Biblio},
month = nov,
title = {{Multi-resolution community detection based on generalized self-loop rescaling strategy}},
url = {http://arxiv.org/abs/1411.2721},
year = {2014}
}
@article{Yun2014,
archivePrefix = {arXiv},
arxivId = {1411.1279},
author = {Yun, Se-Young and Lelarge, Marc and Proutiere, Alexandre},
eprint = {1411.1279},
keywords = {Streaming},
mendeley-tags = {Streaming},
month = nov,
title = {{Streaming, Memory Limited Algorithms for Community Detection}},
url = {http://arxiv.org/abs/1411.1279},
year = {2014}
}
@article{Bruneau2014,
abstract = {This paper describes Cluster Sculptor, a novel interactive clustering system that allows a user to iteratively update the cluster labels of a data set, and an associated low-dimensional projection. The system is fed by clustering results computed in a high-dimensional space, and uses a two-dimensional (2D) projection, both as support for overlaying the cluster labels, and engaging user interaction. By easily interacting with elements directly in the visualization, the user can inject his or her domain knowledge progressively. Via interactive controls, the distribution of the data in the 2D space can be used to amend the cluster labels. Reciprocally, the 2D projection can be updated so as to emphasize the current clusters. The 2D projection updates follow a smooth physical metaphor that gives insight of the process to the user. Updates can be interrupted any time, for further data inspection, or modifying the input preferences. The interest of the system is demonstrated by detailed experimental scenarios on three real data sets.},
annote = {interactive visu},
author = {Bruneau, P. and Pinheiro, P. and Broeksema, B. and Otjacques, B.},
doi = {10.1016/j.neucom.2014.09.062},
file = {:home/gaumont/Documents/1-s2.0-S0925231214012892-main.pdf:pdf},
issn = {09252312},
journal = {Neurocomputing},
keywords = {Dimensionality reduction,Interactive clustering,Visual clustering},
month = nov,
title = {{Cluster Sculptor, an interactive visual clustering system}},
url = {http://www.sciencedirect.com/science/article/pii/S0925231214012892},
year = {2014}
}
@article{Rosvall2011,
abstract = {To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network--the optimal number of levels and modular partition at each level--with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.},
archivePrefix = {arXiv},
arxivId = {1010.0431},
author = {Rosvall, Martin and Bergstrom, Carl T.},
doi = {10.1371/journal.pone.0018209},
eprint = {1010.0431},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Rosvall, Bergstrom - 2011 - Multilevel compression of random walks on networks reveals hierarchical organization in large integrated (2).pdf:pdf},
issn = {19326203},
journal = {PLoS ONE},
pmid = {21494658},
title = {{Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems}},
volume = {6},
year = {2011}
}
@article{He2014,
abstract = {Discovery of communities in complex networks is a fundamental data analysis problem with applications in various domains. While most of the existing approaches have focused on discovering communities of nodes, recent studies have shown the advantages and uses of link community discovery in networks. Generative models provide a promising class of techniques for the identification of modular structures in networks, but most generative models mainly focus on the detection of node communities rather than link communities. In this work, we propose a generative model, which is based on the importance of each node when forming links in each community, to describe the structure of link communities. We proceed to fit the model parameters by taking it as an optimization problem, and solve it using nonnegative matrix factorization. Thereafter, in order to automatically determine the number of communities, we extend the above method by introducing a strategy of iterative bipartition. This extended method not only finds the number of communities all by itself, but also obtains high efficiency, and thus it is more suitable to deal with large and unexplored real networks. We test this approach on both synthetic benchmarks and real-world networks including an application on a large biological network, and compare it with two highly related methods. Results demonstrate the superior performance of our approach over competing methods for the detection of link communities.},
author = {He, Dongxiao and Jin, Di and Baquero, Carlos and Liu, Dayou},
doi = {10.1371/journal.pone.0086899},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/He et al. - 2014 - Link community detection using generative model and nonnegative matrix factorization.pdf:pdf},
issn = {19326203},
journal = {PLoS ONE},
pmid = {24489803},
title = {{Link community detection using generative model and nonnegative matrix factorization}},
volume = {9},
year = {2014}
}
@inproceedings{Prat-Perez2014,
author = {Prat-P\'{e}rez, Arnau and Dom\'{\i}nguez-Sal, David},
booktitle = {GRADES},
title = {{How community-like is the structure of synthetically generated graphs?}},
url = {http://dblp.uni-trier.de/db/conf/sigmod/grades2014.html\#PratD14},
year = {2014}
}
@article{Gauvin2013,
abstract = {The increasing availability of temporal network data is calling for more research on extracting and characterizing mesoscopic structures in temporal networks and on relating such structure to specific functions or properties of the system. An outstanding challenge is the extension of the results achieved for static networks to time-varying networks, where the topological structure of the system and the temporal activity patterns of its components are intertwined. Here we investigate the use of a latent factor decomposition technique, non-negative tensor factorization, to extract the community-activity structure of temporal networks. The method is intrinsically temporal and allows to simultaneously identify communities and to track their activity over time. We represent the time-varying adjacency matrix of a temporal network as a three-way tensor and approximate this tensor as a sum of terms that can be interpreted as communities of nodes with an associated activity time series. We summarize known computational techniques for tensor decomposition and discuss some quality metrics that can be used to tune the complexity of the factorized representation. We subsequently apply tensor factorization to a temporal network for which a ground truth is available for both the community structure and the temporal activity patterns. The data we use describe the social interactions of students in a school, the associations between students and school classes, and the spatio-temporal trajectories of students over time. We show that non-negative tensor factorization is capable of recovering the class structure with high accuracy. In particular, the extracted tensor components can be validated either as known school classes, or in terms of correlated activity patterns, i.e., of spatial and temporal coincidences that are determined by the known school activity schedule.},
author = {Gauvin, Laetitia and Panisson, Andr\'{e} and Cattuto, Ciro},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gauvin, Panisson, Cattuto - 2013 - Detecting the community structure and activity patterns of temporal networks a non-negative tensor fa.pdf:pdf},
journal = {arXiv:1308.0723 [physics]},
keywords = {Computer Science - Social and Information Networks,Physics - Physics and Society},
mendeley-tags = {Computer Science - Social and Information Networks,Physics - Physics and Society},
month = aug,
shorttitle = {Detecting the community structure and activity pat},
title = {{Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach}},
url = {http://arxiv.org/abs/1308.0723 http://www.arxiv.org/pdf/1308.0723.pdf},
year = {2013}
}
@article{Evans2010,
abstract = {In this paper, we develop the idea to partition the edges of a weighted graph in order to uncover overlapping communities of its nodes. Our approach is based on the construction of different types of weighted line graphs, i.e. graphs whose nodes are the links of the original graph, that encapsulate differently the relations between the edges. Weighted line graphs are argued to provide an alternative, valuable representation of the system's topology, and are shown to have important applications in community detection, as the usual node partition of a line graph naturally leads to an edge partition of the original graph. This identification allows us to use traditional partitioning methods in order to address the long-standing problem of the detection of overlapping communities. We apply it to the analysis of different social and geographical networks.},
annote = {Comment: 8 Pages. New title and text revisions to emphasise differences from earlier papers},
author = {Evans, T. S. and Lambiotte, Renaud},
doi = {10.1140/epjb/e2010-00261-8},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Evans, Lambiotte - 2010 - Line Graphs of Weighted Networks for Overlapping Communities(3).pdf:pdf},
issn = {1434-6028, 1434-6036},
journal = {The European Physical Journal B},
keywords = {Computer Science - Data Structures and Algorithms,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,link partition,overlapping},
mendeley-tags = {Computer Science - Data Structures and Algorithms,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,link partition,overlapping},
month = sep,
number = {2},
pages = {265--272},
title = {{Line Graphs of Weighted Networks for Overlapping Communities}},
url = {http://arxiv.org/abs/0912.4389 http://www.arxiv.org/pdf/0912.4389.pdf},
volume = {77},
year = {2010}
}
@article{Lin2008a,
abstract = {We discover communities from social network data, and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. In this novel framework, communities not only generate evolutions, they also are regularized by the temporal smoothness of evolutions. As a result, this framework will discover communities that jointly maximize the fit to the observed data and the temporal evolution. Our approach relies on formulating the problem in terms of non-negative matrix factorization, where communities and their evolutions are factorized in a unified way. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.},
author = {Lin, Yu-ru},
doi = {10.1145/1367497.1367590},
isbn = {9781605580852},
journal = {Social Networks},
pages = {685--694},
title = {{FacetNet : A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks}},
year = {2008}
}
@article{Hopcroft2004,
abstract = {We are interested in tracking changes in large-scale data by periodically creating an agglomerative clustering and examining the evolution of clusters (communities) over time. We examine a large real-world data set: the NEC CiteSeer database, a linked network of >250,000 papers. Tracking changes over time requires a clustering algorithm that produces clusters stable under small perturbations of the input data. However, small perturbations of the CiteSeer data lead to significant changes to most of the clusters. One reason for this is that the order in which papers within communities are combined is somewhat arbitrary. However, certain subsets of papers, called natural communities, correspond to real structure in the CiteSeer database and thus appear in any clustering. By identifying the subset of clusters that remain stable under multiple clustering runs, we get the set of natural communities that we can track over time. We demonstrate that such natural communities allow us to identify emerging communities and track temporal changes in the underlying structure of our network data.},
author = {Hopcroft, John and Khan, Omar and Kulis, Brian and Selman, Bart},
doi = {10.1073/pnas.0307750100},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Hopcroft et al. - 2004 - Tracking evolving communities in large linked networks(3).pdf:pdf},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
keywords = {ALIRE,Cluster Analysis,Databases- Factual,Internet,National Academy of Sciences (U.S.),Neural Networks (Computer),United States},
language = {eng},
mendeley-tags = {ALIRE,Cluster Analysis,Databases- Factual,Internet,National Academy of Sciences (U.S.),Neural Networks (Computer),United States},
month = apr,
pages = {5249--5253},
title = {{Tracking evolving communities in large linked networks}},
url = {http://www.ncbi.nlm.nih.gov/pubmed/14757820},
volume = {101 Suppl},
year = {2004}
}
@article{Figueiredo2012,
author = {Figueiredo, Daniel and Nain, Philippe and Ribeiro, Bruno and {de Souza e Silva}, Edmundo and Towsley, Don},
doi = {10.1145/2318857.2254794},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Figueiredo et al. - 2012 - Characterizing continuous time random walks on time varying graphs(3).pdf:pdf},
isbn = {978-1-4503-1097-0},
issn = {01635999},
journal = {ACM SIGMETRICS Performance Evaluation Review},
keywords = {randomWalk},
mendeley-tags = {randomWalk},
month = jun,
number = {1},
pages = {307},
publisher = {ACM},
title = {{Characterizing continuous time random walks on time varying graphs}},
url = {http://dl.acm.org/citation.cfm?id=2318857.2254794},
volume = {40},
year = {2012}
}
@article{Eppstein2011,
abstract = {We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, L$\backslash$"offler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoretical Computer Science, 2006) in practice. However, the algorithm of Tomita et al. uses an adjacency matrix, which requires too much space for large sparse graphs. Our new algorithm opens the door for fast analysis of large sparse graphs whose adjacency matrix will not fit into working memory.},
archivePrefix = {arXiv},
arxivId = {1103.0318},
author = {Eppstein, David and Strash, Darren},
eprint = {1103.0318},
month = mar,
pages = {12},
title = {{Listing All Maximal Cliques in Large Sparse Real-World Graphs}},
url = {http://arxiv.org/abs/1103.0318},
year = {2011}
}
@article{Gopalan2013,
abstract = {Detecting overlapping communities is essential to analyzing and exploring natural networks such as social networks, biological networks, and citation networks. However, most existing approaches do not scale to the size of networks that we regularly observe in the real world. In this paper, we develop a scalable approach to community detection that discovers overlapping communities in massive real-world networks. Our approach is based on a Bayesian model of networks that allows nodes to participate in multiple communities, and a corresponding algorithm that naturally interleaves subsampling from the network and updating an estimate of its communities. We demonstrate how we can discover the hidden community structure of several real-world networks, including 3.7 million US patents, 575,000 physics articles from the arXiv preprint server, and 875,000 connected Web pages from the Internet. Furthermore, we demonstrate on large simulated networks that our algorithm accurately discovers the true community structure. This paper opens the door to using sophisticated statistical models to analyze massive networks.},
author = {Gopalan, Prem K and Blei, David M},
doi = {10.1073/pnas.1221839110},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
keywords = {Algorithms,Bayes Theorem,Community Networks,Computer Simulation,Humans,Models, Statistical,Social Behavior,Stochastic Processes},
pages = {14534--9},
pmid = {23950224},
title = {{Efficient discovery of overlapping communities in massive networks.}},
url = {http://www.pnas.org/content/early/2013/08/14/1221839110},
volume = {110},
year = {2013}
}
@article{Dutta2014,
abstract = {A good knowledge of the specificities of the animal trade network is highly valuable to better control pathogen spread on a large regional to transnational scale. Because of their temporal dynamical nature, studying multi-annual datasets is particularly needed to investigate whether structural patterns are stable over the years. In this study, we analysed the French cattle movement network from 2005 to 2009 for different spatial granularities and temporal windows, with the three-fold objective of exploring temporal variations of the main network characteristics, computing proxies for pathogen spread on this network, which accounts for its time-varying properties and identifying specificities related to the main types of animals and farms (dairy versus beef). Network properties did not qualitatively vary among different temporal and spatial granularities. About 40\% of the holdings and 80\% of the communes were directly interconnected. The width of the aggregation time window barely impacted normalised distributions of indicators. A period of 8 to 16 weeks would suffice for robust estimation of their main trends, whereas longer periods would provide more details on tails. The dynamic nature of the network could be seen through the small overlap between consecutive networks with 65\% of common active nodes for only 3\% of common links over 2005-2009. To control pathogen spread on such a network, by reducing the largest strongly connected component by more than 80\%, movements should be prevented from 1 to 5\% of the holdings with the highest centrality in the previous year network. The analysis of breed-wise and herd-wise subnetworks, dairy, beef and mixed, reveals similar trends in temporal variation of average indicators and their distributions. The link-based backbones of beef subnetworks seem to be more stable over time than those of other subnetworks. At a regional scale, node reachability accounting for time-respecting paths, as proxy of epidemic burden, is greater for a dairy region than for a beef region. This highlights the importance of considering local specificities and temporal dynamics of animal trade networks when evaluating control measures of pathogen spread.},
author = {Dutta, Bhagat Lal and Ezanno, Pauline and Vergu, Elisabeta},
doi = {10.1016/j.prevetmed.2014.09.005},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Dutta, Ezanno, Vergu - 2014 - Characteristics of the spatio-temporal network of cattlemovements in France over a 5-year period.pdf:pdf},
issn = {01675877},
journal = {Preventive Veterinary Medicine},
keywords = {Livestock movements,Network analysis,disease control,dynamic networks,epidemiological modelling,surveillance},
month = sep,
title = {{Characteristics of the spatio-temporal network of cattlemovements in France over a 5-year period}},
url = {http://www.sciencedirect.com/science/article/pii/S0167587714002943},
year = {2014}
}
@article{Lancichinetti2008,
abstract = {Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.},
annote = {From Duplicate 2 ( },
archivePrefix = {arXiv},
arxivId = {0805.4770},
author = {Lancichinetti, Andrea and Fortunato, Santo and Radicchi, Filippo},
doi = {10.1103/PhysRevE.78.046110},
eprint = {0805.4770},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato, Radicchi - 2008 - Benchmark graphs for testing community detection algorithms(4).pdf:pdf},
isbn = {1539-3755 (Print)},
issn = {1539-3755},
journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
keywords = {Benchmark},
language = {eng},
mendeley-tags = {Benchmark},
month = oct,
number = {4 Pt 2},
pages = {046110},
pmid = {18999496},
title = {{Benchmark graphs for testing community detection algorithms.}},
url = {http://www.ncbi.nlm.nih.gov/pubmed/18999496},
volume = {78},
year = {2008}
}
@article{Sarzynska2014,
abstract = {In the study of networks, it is often insightful to use algorithms to determine mesoscale features such as "community structure", in which densely connected sets of nodes constitute "communities" that have sparse connections to other communities. The most popular way of detecting communities algorithmically is to optimize the quality function known as modularity. When optimizing modularity, one compares the actual connections in a (static or time-dependent) network to the connections obtained from a random-graph ensemble that acts as a null model. The communities are then the sets of nodes that are connected to each other densely relative to what is expected from the null model. Clearly, the process of community detection depends fundamentally on the choice of null model, so it is important to develop and analyze novel null models that take into account appropriate features of the system under study. In this paper, we investigate the effects of using null models that take incorporate spatial information, and we propose a novel null model based on the radiation model of population spread. We also develop novel synthetic spatial benchmark networks in which the connections between entities are based on distance or flux between nodes, and we compare the performance of both static and time-dependent radiation null models to the standard ("Newman-Girvan") null model for modularity optimization and a recently-proposed gravity null model. In our comparisons, we use both the above synthetic benchmarks and time-dependent correlation networks that we construct using countrywide dengue fever incidence data for Peru. We also evaluate a recently-proposed correlation null model, which was developed specifically for correlation networks that are constructed from time series, on the epidemic-correlation data.},
archivePrefix = {arXiv},
arxivId = {1407.6297},
author = {Sarzynska, Marta and Leicht, Elizabeth A. and Chowell, Gerardo and Porter, Mason A.},
eprint = {1407.6297},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Sarzynska et al. - 2014 - Null Models for Community Detection in Spatially-Embedded, Temporal Networks(3).pdf:pdf},
month = jul,
title = {{Null Models for Community Detection in Spatially-Embedded, Temporal Networks}},
url = {http://arxiv.org/abs/1407.6297},
year = {2014}
}
@inproceedings{Seifi2012,
abstract = {Community structure is a key property of complex networks. Many algorithms have been proposed to automatically detect communities in static networks but few studies have considered the detection and tracking of communities in an evolving network. Tracking the evolution of a given community over time requires a clustering algorithm that produces stable clusters. However, most community detection algorithms are very unstable and therefore unusable for evolving networks. In this paper, we apply the methodology proposed in [seifi2012] to detect what we call community cores in evolving networks. We show that cores are much more stable than "classical" communities and that we can overcome the disadvantages of the stabilized methods.},
address = {New York, NY, USA},
author = {Seifi, Massoud and Guillaume, Jean-Loup},
doi = {10.1145/2187980.2188258},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Seifi, Guillaume - 2012 - Community cores in evolving networks(3).pdf:pdf},
isbn = {978-1-4503-1230-1},
keywords = {ALIRE,community cores,community structure,complex networks,evolving networks},
mendeley-tags = {ALIRE,community cores,community structure,complex networks,evolving networks},
pages = {1173--1180},
publisher = {ACM},
series = {WWW '12 Companion},
title = {{Community cores in evolving networks}},
url = {http://doi.acm.org/10.1145/2187980.2188258 http://dl.acm.org/ft\_gateway.cfm?id=2188258\&type=pdf},
year = {2012}
}
@article{Zhou2014a,
abstract = {Online community detection is essential for social network analysis. Modularity is a quality function used to measure the strength of the community structure discovered with social networks. Existing methods detect community structures through modularity analysis. However, the existing modularities are unable to identify community structures correctly when communities are very different in size, in particular, when the size of some communities is very small compared with others. To address this problem, we propose the concept of a coupling coefficient between two communities and define a new modularity, MC modularity, to evaluate the quality of the discovered community structures. This method can provide adequate measures for the quality of community structures. In addition, we develop the DC\_MC algorithm to detect community structures based on the concept of MC modularity. An algorithm for shifting a group of nodes, instead of one node at a time, amongst communities also is designed to achieve optimal results. The effectiveness and efficacy of the approach we proposed have been demonstrated through a set of experiments involving real data benchmarks and synthetic data sets that are purpose-built for evaluating different types of networks.},
annote = {Modified Modularity},
author = {Zhou, L. and Lu, K.},
doi = {10.1093/comjnl/bxu087},
issn = {0010-4620},
journal = {The Computer Journal},
month = sep,
pages = {bxu087--},
title = {{Detecting Communities with Different Sizes for Social Network Analysis}},
url = {http://comjnl.oxfordjournals.org/content/early/2014/09/21/comjnl.bxu087.abstract},
year = {2014}
}
@inproceedings{Pan2011,
abstract = {Detecting communities from networks has been given great attention these years. The traditional approaches were always focusing on the node community, while some recent studies have shown great advantage of link community approach which partitions links instead of nodes into communities. We proposed a novel algorithm LBLC (local based link community) to detect link communities in the network based on local information. A local link community can be detected by maximizing a local link fitness function from a seed link, which was ranked by another algorithm previously. The proposed LBLC algorithm has been tested on both synthetic and real world networks, and it has been compared with other link community detecting algorithm. The experimental results showed LBLC achieves significant improvement on link community structure.},
author = {Pan, Lei and Wang, Chongjun and Xie, Junyuan and Liu, Meilin},
doi = {10.1109/ICTAI.2011.140},
keywords = {Dolphins,Educational institutions,Equations,Image edge detection,LBLC algorithm,Link Community,Physics,Social network services,communities,community detection,comp,functions,link partition,local based link community detection,local community,local information,local link fitness function maximisation,network theory (graphs),optimisation,real world networks,seed link,synthetic networks},
mendeley-tags = {Dolphins,Educational institutions,Equations,Image edge detection,LBLC algorithm,Link Community,Physics,Social network services,communities,community detection,comp,functions,link partition,local based link community detection,local community,local information,local link fitness function maximisation,network theory (graphs),optimisation,real world networks,seed link,synthetic networks},
pages = {884--886},
title = {{Detecting Link Communities Based on Local Approach}},
year = {2011}
}
@article{Kim2014,
author = {Kim, Sungmin},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kim - 2014 - Community Detection in Directed Networks and its Application to Analysis of Social Networks(4).pdf:pdf},
keywords = {Bibliographie,Conductance},
mendeley-tags = {Bibliographie,Conductance},
title = {{Community Detection in Directed Networks and its Application to Analysis of Social Networks}},
year = {2014}
}
@incollection{Gregory2007,
abstract = {Recent years have seen the development of many graph clustering algorithms, which can identify community structure in networks. The vast majority of these only find disjoint communities, but in many real-world networks communities overlap to some extent. We present a new algorithm for discovering overlapping communities in networks, by extending Girvan and Newman’s well-known algorithm based on the betweenness centrality measure. Like the original algorithm, ours performs hierarchical clustering — partitioning a network into any desired number of clusters — but allows them to overlap. Experiments confirm good performance on randomly generated networks based on a known overlapping community structure, and interesting results have also been obtained on a range of real-world networks.},
author = {Gregory, Steve},
editor = {Kok, Joost N. and Koronacki, Jacek and de Mantaras, Ramon Lopez and Matwin, Stan and Mladeni\v{c}, Dunja and Skowron, Andrzej},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gregory - 2007 - An Algorithm to Find Overlapping Community Structure in Networks(3).pdf:pdf},
isbn = {978-3-540-74975-2, 978-3-540-74976-9},
keywords = {Artificial Intelligence (incl. Robotics),Database Management,Document Preparation and Text Processing,Information Storage and Retrieval,Mathematical Logic and Formal Languages,Probability and Statistics in Computer Science,overlapping},
mendeley-tags = {Artificial Intelligence (incl. Robotics),Database Management,Document Preparation and Text Processing,Information Storage and Retrieval,Mathematical Logic and Formal Languages,Probability and Statistics in Computer Science,overlapping},
month = jan,
pages = {91--102},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{An Algorithm to Find Overlapping Community Structure in Networks}},
url = {http://link.springer.com/chapter/10.1007/978-3-540-74976-9\_12 http://link.springer.com/content/pdf/10.1007/978-3-540-74976-9\_12.pdf},
year = {2007}
}
@article{Xin2014,
abstract = {The traditional semantic social network (SSN) community detection algorithms need to preset the number of the communities and couldn’t detect the overlapping communities. To solve the issue of presetting the number of communities, we present a clustering algorithm for community detection based on the link-field-topic (LFT) model suggested. For the process of clustering is independent of context sampling, the number of communities is not necessary to be preset. To solve the issue of overlapping community detection, we establish the semantic link weight (SLW) depending on the analysis of LFT, to evaluate the semantic weight of links for each sampling field. The proposed clustering algorithm is based on the SLW which could separate the SSN into clustering units. As a result, the intersection on several units is the overlapping part. Finally, we establish semantic modularity (SQ) involving SQ1 and SQ2 for the evaluation of the detected semantic communities. The efficiency and feasibility of the LFT model and the semantic modularity is verified by experimental analysis.},
author = {Xin, Yu and Yang, Jing and Xie, Zhi-Qiang},
doi = {10.1016/j.eswa.2014.07.009},
file = {:home/gaumont/Documents/1-s2.0-S0957417414004072-main.pdf:pdf},
issn = {09574174},
journal = {Expert Systems with Applications},
keywords = {Community Detection,Overlapping Communities,Semantic Modularity,Semantic Social Network},
month = aug,
title = {{A Semantic Overlapping Community Detection Algorithm Based on Field Sampling}},
url = {http://www.sciencedirect.com/science/article/pii/S0957417414004072},
year = {2014}
}
@article{Gauvin2015,
abstract = {The customary perspective to reason about epidemic mitigation in temporal networks hinges on the identification of nodes with specific features or network roles. The ensuing individual-based control strategies, however, are difficult to carry out in practice and ignore important correlations between topological and temporal patterns. Here we adopt a mesoscopic perspective and present a principled framework to identify collective features at multiple scales and rank their importance for epidemic spread. We use tensor decomposition techniques to build an additive representation of a temporal network in terms of mesostructures, such as cohesive clusters and temporally-localized mixing patterns. This representation allows to determine the impact of individual mesostructures on epidemic spread and to assess the effect of targeted interventions that remove chosen structures. We illustrate this approach using high-resolution social network data on face-to-face interactions in a school and show that our method affords the design of effective mesoscale interventions.},
archivePrefix = {arXiv},
arxivId = {1501.02758},
author = {Gauvin, Laetitia and Panisson, Andr\'{e} and Barrat, Alain and Cattuto, Ciro},
eprint = {1501.02758},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gauvin et al. - 2015 - Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread.pdf:pdf},
month = jan,
title = {{Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread}},
url = {http://arxiv.org/abs/1501.02758},
year = {2015}
}
@article{Chi2014,
annote = {Application r\'{e}seau},
author = {Chi, Guanghua and Thill, Jean‐Claude and Tong, Daoqin and Shi, Li and Liu, Yu},
doi = {10.1111/pirs.12149},
issn = {1435-5957},
journal = {Papers in Regional Science},
keywords = {C18,R11,R58,Spatial network,betweenness centrality,community detection,mobile phone data,regional structure},
language = {en},
month = dec,
title = {{Uncovering regional characteristics from mobile phone data: A network science approach}},
url = {http://onlinelibrary.wiley.com/doi/10.1111/pirs.12149/full},
year = {2014}
}
@article{Jin,
author = {Jin, Jiahui and Khemmarat, Samamon and Gao, Lixin and Luo, Junzhou},
file = {:home/gaumont/Documents/www2015\_submission\_580.pdf:pdf},
title = {{Querying Web-Scale Information Networks Through Bounding Matching Scores}}
}
@inproceedings{Lim2014,
author = {Lim, Sungsu and Ryu, Seungwoo and Kwon, Sejeong and Jung, Kyomin and Lee, Jae-Gil},
booktitle = {2014 IEEE 30th International Conference on Data Engineering},
doi = {10.1109/ICDE.2014.6816659},
file = {:home/gaumont/Documents/ICDE14-Lim.pdf:pdf},
isbn = {978-1-4799-2555-1},
keywords = {Clustering algorithms,Communities,Detection algorithms,Educational institutions,Kernel,Lifting equipment,Social network services},
language = {English},
month = mar,
pages = {292--303},
publisher = {IEEE},
title = {{LinkSCAN*: Overlapping community detection using the link-space transformation}},
url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6816659},
year = {2014}
}
@article{Zhang2015,
abstract = {Normalized Mutual Information (NMI) has been widely used to evaluate accuracy of community detection algorithms. In this notes we show that NMI is seriously affected by systematic error due to finite size of networks, and may give wrong estimate of performance of algorithms in some cases. A simple expression for the estimate of this error is derived and tested numerically. We suggest to use a new measure to accuracy of community detection, namely relative Normalized Mutual Information (rNMI), which is NMI minus the expected NMI of random partitions. This measure is very close to zero for two random partitions even with a short length, so it can overcome the problem of NMI.},
archivePrefix = {arXiv},
arxivId = {1501.03844},
author = {Zhang, Pan},
eprint = {1501.03844},
month = jan,
title = {{A revisit to evaluating accuracy of community detection using the normalized mutual information}},
url = {http://arxiv.org/abs/1501.03844},
year = {2015}
}
@article{DeReus2014,
abstract = {Brain function depends on efficient processing and integration of information within a complex network of neural interactions, known as the connectome. An important aspect of connectome architecture is the existence of community structure, providing an anatomical basis for the occurrence of functional specialization. Typically, communities are defined as groups of densely connected network nodes, representing clusters of brain regions. Looking at the connectome from a different perspective, instead focusing on the interconnecting links or edges, we find that the white matter pathways between brain regions also exhibit community structure. Eleven link communities were identified: five spanning through the midline fissure, three through the left hemisphere and three through the right hemisphere. We show that these link communities are consistently identifiable and investigate the network characteristics of their underlying white matter pathways. Furthermore, examination of the relationship between link communities and brain regions revealed that the majority of brain regions participate in multiple link communities. In particular, the highly connected and central hub regions showed a rich level of community participation, supporting the notion that these hubs play a pivotal role as confluence zones in which neural information from different domains merges.},
author = {de Reus, Marcel A and Saenger, Victor M and Kahn, Ren\'{e} S and van den Heuvel, Martijn P},
doi = {10.1098/rstb.2013.0527},
issn = {1471-2970},
journal = {Philosophical transactions of the Royal Society of London. Series B, Biological sciences},
language = {en},
month = oct,
number = {1653},
pages = {20130527},
pmid = {25180305},
publisher = {The Royal Society},
title = {{An edge-centric perspective on the human connectome: link communities in the brain.}},
url = {http://royalsocietypublishing.org/content/369/1653/20130527.abstract},
volume = {369},
year = {2014}
}
@article{Kawamoto2015,
author = {Kawamoto, Tatsuro and Rosvall, Martin},
doi = {10.1103/PhysRevE.91.012809},
issn = {1539-3755},
journal = {Physical Review E},
month = jan,
number = {1},
pages = {012809},
title = {{Estimating the resolution limit of the map equation in community detection}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.91.012809},
volume = {91},
year = {2015}
}
@article{Nicosia2009,
abstract = {Complex networks topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of modularity function, given by M. Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new dataset which could be used as a reference benchmark for overlapping community structures identification.},
author = {Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M.},
doi = {10.1088/1742-5468/2009/03/P03024},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Nicosia et al. - 2009 - Extending the definition of modularity to directed graphs with overlapping communities(3).pdf:pdf},
issn = {1742-5468},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
keywords = {Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,directed graph,overlapping,overlapping community},
mendeley-tags = {Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,directed graph,overlapping,overlapping community},
month = mar,
number = {03},
pages = {P03024},
title = {{Extending the definition of modularity to directed graphs with overlapping communities}},
url = {http://arxiv.org/abs/0801.1647 http://www.arxiv.org/pdf/0801.1647.pdf},
volume = {2009},
year = {2009}
}
@article{Meila2007,
abstract = {This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set. The criterion, called variation of information (VI), measures the amount of information lost and gained in changing from clustering C to clustering C′. The basic properties of VI are presented and discussed. We focus on two kinds of properties: (1) those that help one build intuition about the new criterion (in particular, it is shown the VI is a true metric on the space of clusterings), and (2) those that pertain to the comparability of VI values over different experimental conditions. As the latter properties have rarely been discussed explicitly before, other existing comparison criteria are also examined in their light. Finally we present the VI from an axiomatic point of view, showing that it is the only "sensible" criterion for comparing partitions that is both aligned to the lattice and convexely additive. As a consequence, we prove an impossibility result for comparing partitions: there is no criterion for comparing partitions that simultaneously satisfies the above two desirable properties and is bounded. © 2007 Elsevier Inc. All rights reserved.},
annote = {Variation of information},
author = {Meilǎ, Marina},
doi = {10.1016/j.jmva.2006.11.013},
isbn = {0047-259X},
issn = {0047259X},
journal = {Journal of Multivariate Analysis},
keywords = {Agreement measures,Clustering,Comparing partitions,Information theory,Mutual information,Similarity measures},
pages = {873--895},
title = {{Comparing clusterings-an information based distance}},
volume = {98},
year = {2007}
}
@article{Orman2014,
abstract = {Many methods have been proposed to detect communities, not only in plain, but also in attributed, directed or even dynamic complex networks. In its simplest form, a community structure takes the form of a partition of the node set. From the modeling point of view, to be of some utility, this partition must then be characterized relatively to the properties of the studied system. However, if most of the existing works focus on defining methods for the detection of communities, only very few try to tackle this interpretation problem. Moreover, the existing approaches are limited either in the type of data they handle, or by the nature of the results they output. In this work, we propose a method to efficiently support such a characterization task. We first define a sequence-based representation of networks, combining temporal information, topological measures, and nodal attributes. We then describe how to identify the most emerging sequential patterns of this dataset, and use them to characterize the communities. We also show how to detect unusual behavior in a community, and highlight outliers. Finally, as an illustration, we apply our method to a network of scientific collaborations.},
annote = {les attributs ne sont pas dynamique},
archivePrefix = {arXiv},
arxivId = {1406.6597},
author = {Orman, G\"{u}nce Keziban and Labatut, Vincent and Plantevit, Marc and Boulicaut, Jean-Fran\c{c}ois},
eprint = {1406.6597},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Orman et al. - 2014 - A Method for Characterizing Communities in Dynamic Attributed Complex Networks(4).pdf:pdf},
month = jun,
title = {{A Method for Characterizing Communities in Dynamic Attributed Complex Networks}},
url = {http://arxiv.org/abs/1406.6597},
year = {2014}
}
@techreport{Hoffmann2013,
abstract = {In the study of dynamical processes on networks, there has been intense focus on network structure -- i.e., the arrangement of edges and their associated weights -- but the effects of the temporal patterns of edges remains poorly understood. In this chapter, we develop a mathematical framework for random walks on temporal networks using an approach that provides a compromise between abstract but unrealistic models and data-driven but non-mathematical approaches. To do this, we introduce a stochastic model for temporal networks in which we summarize the temporal and structural organization of a system using a matrix of waiting-time distributions. We show that random walks on stochastic temporal networks can be described exactly by an integro-differential master equation and derive an analytical expression for its asymptotic steady state. We also discuss how our work might be useful to help build centrality measures for temporal networks.},
annote = {Comment: Chapter in Temporal Networks (Petter Holme and Jari Saramaki editors). Springer. Berlin, Heidelberg 2013. The book chapter contains minor corrections and modifications. This chapter is based on arXiv:1112.3324, which contains additional calculations and numerical simulations},
author = {Hoffmann, Till and Porter, Mason A. and Lambiotte, Renaud},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Hoffmann, Porter, Lambiotte - 2013 - Random Walks on Stochastic Temporal Networks(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Hoffmann, Porter, Lambiotte - 2013 - Random Walks on Stochastic Temporal Networks(3).html:html},
keywords = {Computer Science - Social and Information Networks,Physics - Physics and Society},
mendeley-tags = {Computer Science - Social and Information Networks,Physics - Physics and Society},
month = jun,
title = {{Random Walks on Stochastic Temporal Networks}},
url = {http://arxiv.org/abs/1306.0715 http://www.arxiv.org/pdf/1306.0715.pdf},
year = {2013}
}
@article{Ahn2010a,
abstract = {Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society. One crucial step when studying the structure and dynamics of networks is to identify communities: groups of related nodes that correspond to functional subunits such as protein complexes or social spheres. Communities in networks often overlap such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure. However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks, including major biological networks such as protein–protein interaction and metabolic networks, and show that a large social network contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.},
annote = {Source code},
author = {Ahn, Yong-Yeol and Bagrow, James P. and Lehmann, Sune},
doi = {10.1038/nature09182},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ahn, Bagrow, Lehmann - 2010 - Link communities reveal multiscale complexity in networks(8).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Ahn, Bagrow, Lehmann - 2010 - Link communities reveal multiscale complexity in networks(7).pdf:pdf},
issn = {0028-0836},
journal = {Nature},
keywords = {Applied physics,Engineering,Society,link community,overlapping,printed},
language = {en},
mendeley-tags = {Applied physics,Engineering,Society,link community,overlapping,printed},
month = aug,
number = {7307},
pages = {761--764},
title = {{Link communities reveal multiscale complexity in networks}},
url = {http://www.nature.com/nature/journal/v466/n7307/abs/nature09182.html http://www.nature.com/nature/journal/v466/n7307/pdf/nature09182.pdf http://dx.doi.org/10.1038/nature09182},
volume = {466},
year = {2010}
}
@article{Malliaros2014,
annote = {robustesse},
author = {Malliaros, Fragkiskos D. and Megalooikonomou, Vasileios and Faloutsos, Christos},
doi = {10.1007/s10115-014-0810-7},
issn = {0219-1377},
journal = {Knowledge and Information Systems},
month = dec,
title = {{Estimating robustness in large social graphs}},
url = {http://link.springer.com/10.1007/s10115-014-0810-7},
year = {2014}
}
@article{Eckmann2004a,
abstract = {We study the dynamic network of e-mail traffic and find that it develops self-organized coherent structures similar to those appearing in many nonlinear dynamic systems. Such structures are uncovered by a general information theoretic approach to dynamic networks based on the analysis of synchronization among trios of users. In the e-mail network, coherent structures arise from temporal correlations when users act in a synchronized manner. These temporally linked structures turn out to be functional, goal-oriented aggregates that must react in real time to changing objectives and challenges (e.g., committees at a university). In contrast, static structures turn out to be related to organizational units (e.g., departments).},
author = {Eckmann, Jean-Pierre and Moses, Elisha and Sergi, Danilo},
doi = {10.1073/pnas.0405728101},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Eckmann, Moses, Sergi - 2004 - Entropy of dialogues creates coherent structures in e-mail traffic(4).pdf:pdf},
isbn = {0027-8424$\backslash$n1091-6490},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
month = oct,
number = {40},
pages = {14333--7},
pmid = {15448210},
title = {{Entropy of dialogues creates coherent structures in e-mail traffic.}},
url = {http://www.pnas.org/cgi/content/long/101/40/14333 http://www.pnas.org/content/101/40/14333},
volume = {101},
year = {2004}
}
@article{Kim2014a,
abstract = {Most community detection methods use network topology and edge density to identify optimal communities. However, in these methods, several objects that are connected by high weights may be decomposed into different communities, even when they intuitively belong to a single community. In this case, it is more effective to classify the objects into the same community because they perform important roles in controlling and understanding the network. To achieve this goal, in this paper, we propose a method of detecting optimal community structures in a complex network using interaction-based edge clustering. Our approach is to consider network topology as well as interaction density when identifying overlapping and hierarchical communities. Additionally, we measure the differences between the quantity and quality of intra- and inter-community interactions to evaluate the quality of the community structure. We test our method on several benchmark networks with known community structures. Additionally, after applying our method to several real-world complex networks, we evaluate our method through comparison with other methods. We find that the community quality and the overlap quality for our method surpass the results of the other methods.},
author = {Kim, Paul and Kim, Sangwook},
doi = {10.1016/j.physa.2014.09.035},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kim, Kim - 2014 - Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering.pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Community detection,Complex network,Edge clustering,Hierarchical structure,Overlapping communities},
month = sep,
title = {{Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437114007936},
year = {2014}
}
@article{Tang2012,
abstract = {This study of collective behavior is to understand how individuals behave in a social networking environment. Oceans of data generated by social media like Facebook, Twitter, Flickr, and YouTube present opportunities and challenges to study collective behavior on a large scale. In this work, we aim to learn to predict collective behavior in social media. In particular, given information about some individuals, how can we infer the behavior of unobserved individuals in the same network? A social-dimension-based approach has been shown effective in addressing the heterogeneity of connections presented in social media. However, the networks in social media are normally of colossal size, involving hundreds of thousands of actors. The scale of these networks entails scalable learning of models for collective behavior prediction. To address the scalability issue, we propose an edge-centric clustering scheme to extract sparse social dimensions. With sparse social dimensions, the proposed approach can efficiently handle networks of millions of actors while demonstrating a comparable prediction performance to other nonscalable methods.},
author = {Tang, Lei and Wang, Xufei and Liu, Huan},
doi = {10.1109/TKDE.2011.38},
file = {:home/gaumont/Documents/TKDE.pdf:pdf},
isbn = {10.1109/TKDE.2011.38},
issn = {1041-4347},
journal = {IEEE Transactions on Knowledge and Data Engineering},
keywords = {Classification with network data,collective behavior,community detection,social dimensions.},
language = {English},
month = jun,
number = {6},
pages = {1080--1091},
publisher = {IEEE Computer Society},
title = {{Scalable Learning of Collective Behavior}},
url = {http://www.computer.org/csdl/trans/tk/2012/06/ttk2012061080.html},
volume = {24},
year = {2012}
}
@article{Yan2012a,
abstract = {Research topics and research communities are not disconnected from each other: communities and topics are interwoven and co-evolving. Yet, scientometric evaluations of topics and communities have been conducted independently and synchronically, with researchers often relying on homogeneous unit of analysis, such as authors, journals, institutions, or topics. Therefore, new methods are warranted that examine the dynamic relationship between topics and communities. This paper examines how research topics are mixed and matched in evolving research communities by using a hybrid approach which integrates both topic identification and community detection techniques. Using a data set on information retrieval (IR) publications, two layers of enriched information are constructed and contrasted: one is the communities detected through the topology of coauthorship network and the other is the topics of the communities detected through the topic model. We find evidence to support the assumption that IR communities and topics are interwoven and co-evolving, and topics can be used to understand the dynamics of community structures. We recommend the use of the hybrid approach to study the dynamic interactions of topics and communities. ?? 2011 Elsevier Ltd.},
author = {Yan, Erjia and Ding, Ying and Milojevi??, Sta??a and Sugimoto, Cassidy R.},
doi = {10.1016/j.joi.2011.10.001},
issn = {17511577},
journal = {Journal of Informetrics},
keywords = {Coauthorship,Community,Knowledge discovery,Latent Dirichlet Allocation,Network},
pages = {140--153},
title = {{Topics in dynamic research communities: An exploratory study for the field of information retrieval}},
volume = {6},
year = {2012}
}
@article{BOCCALETTI2006,
author = {BOCCALETTI, S and LATORA, V and MORENO, Y and CHAVEZ, M and HWANG, D},
doi = {10.1016/j.physrep.2005.10.009},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/BOCCALETTI et al. - 2006 - Complex networks Structure and dynamics(4).pdf:pdf},
issn = {03701573},
journal = {Physics Reports},
language = {en},
month = feb,
number = {4-5},
pages = {175--308},
title = {{Complex networks: Structure and dynamics}},
url = {http://adsabs.harvard.edu/abs/2006PhR...424..175B},
volume = {424},
year = {2006}
}
@article{Wu2014,
abstract = {The clustering phenomenon is common in real world networks. A discrete-time network model is proposed firstly in this paper, and then the phase clustering dynamics of the networks are studied carefully. The proposed model acts as a bridge between the dynamic phenomenon and the topology of a modular network. On one hand, phase clustering phenomenon will occur for a modular network by the proposed model; on the other hand, the communities can be identified from the clustering phenomenon. Beyond the phases\&apos; information, it is found that the frequencies of phases can be applied to community detection also with the proposed model. In specific, communities are identified from the information of phases and their frequencies of the nodes. Detailed algorithm for community detection is provided. Experiments show that the performance and efficiency of the dynamics based algorithm are competitive with recent modularity based algorithms in large scale networks.},
author = {Wu, Jianshe and Jiao, Yang},
doi = {10.1063/1.4886695},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Wu, Jiao - 2014 - Clustering dynamics of complex discrete-time networks and its application in community detection(3).pdf:pdf},
issn = {1054-1500},
journal = {Chaos: An Interdisciplinary Journal of Nonlinear Science},
month = sep,
number = {3},
pages = {033104},
publisher = {AIP Publishing},
title = {{Clustering dynamics of complex discrete-time networks and its application in community detection}},
url = {http://scitation.aip.org/content/aip/journal/chaos/24/3/10.1063/1.4886695},
volume = {24},
year = {2014}
}
@article{Newman2001,
annote = {con},
author = {Newman, M. E. J. and Strogatz, S. H. and Watts, D. J.},
doi = {10.1103/PhysRevE.64.026118},
issn = {1063-651X},
journal = {Physical Review E},
keywords = {configuration model},
mendeley-tags = {configuration model},
month = jul,
number = {2},
pages = {026118},
title = {{Random graphs with arbitrary degree distributions and their applications}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.64.026118},
volume = {64},
year = {2001}
}
@inproceedings{Amelio2014,
address = {New York, New York, USA},
author = {Amelio, Alessia and Pizzuti, Clara},
booktitle = {Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion - GECCO Comp '14},
doi = {10.1145/2598394.2598453},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Amelio, Pizzuti - 2014 - Uncovering communities in multidimensional networks with multiobjective genetic algorithms(3).pdf:pdf},
isbn = {9781450328814},
keywords = {community detection,genetic algorithms,multi-dimensional networks,multiobjective},
month = jul,
pages = {75--76},
publisher = {ACM Press},
title = {{Uncovering communities in multidimensional networks with multiobjective genetic algorithms}},
url = {http://dl.acm.org/citation.cfm?id=2598394.2598453},
year = {2014}
}
@article{Lambiotte2011,
abstract = {The behavior of complex systems is determined not only by the topological organization of their interconnections but also by the dynamical processes taking place among their constituents. A faithful modeling of the dynamics is essential because different dynamical processes may be affected very differently by network topology. A full characterization of such systems thus requires a formalization that encompasses both aspects simultaneously, rather than relying only on the topological adjacency matrix. To achieve this, we introduce the concept of flow graphs, namely weighted networks where dynamical flows are embedded into the link weights. Flow graphs provide an integrated representation of the structure and dynamics of the system, which can then be analyzed with standard tools from network theory. Conversely, a structural network feature of our choice can also be used as the basis for the construction of a flow graph that will then encompass a dynamics biased by such a feature. We illustrate the ideas by focusing on the mathematical properties of generic linear processes on complex networks that can be represented as biased random walks and their dual consensus dynamics, and show how our framework improves our understanding of these processes.},
author = {Lambiotte, Renaud and Sinatra, R. and Delvenne, J.-C. and Evans, T. S. and Barahona, M. and Latora, V.},
doi = {10.1103/PhysRevE.84.017102},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lambiotte et al. - 2011 - Flow graphs Interweaving dynamics and structure(5).pdf:pdf},
journal = {Physical Review E},
month = jul,
number = {1},
pages = {017102},
shorttitle = {Flow graphs},
title = {{Flow graphs: Interweaving dynamics and structure}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.84.017102},
volume = {84},
year = {2011}
}
@article{Nascimento2013a,
abstract = {Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. The modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem. In this paper we present a Greedy Randomized Adaptive Search Procedure (GRASP) with path relinking, for solving the modularity maximization problem in weighted graphs. A class of \{0,1\} matrices is introduced that characterizes the family of clusterings in a graph, and a distance function is given that enables us to define an l-neighborhood local search, which generalizes most of the related local search methods that have appeared in the literature. Computational experiments comparing the proposed algorithm with other heuristics from the literature in a set of artificially generated graphs and some well known benchmark instances, indicate that our implementation of GRASP with path relinking consistently produces better quality solutions. ?? 2013 Elsevier Ltd. All rights reserved.},
annote = {From Duplicate 3 ( },
archivePrefix = {arXiv},
arxivId = {arxiv.org/1006.1788},
author = {Evans, T. S. and Lambiotte, Renaud and Panzarasa, P. and Nascimento, Mari?? C V and Pitsoulis, Leonidas},
doi = {10.1016/j.cor.2013.03.002},
eprint = {1006.1788},
isbn = {0138-9130},
issn = {03050548},
journal = {Computers and Operations Research},
keywords = {Collaboration networks,Community structure,Complex systems,GRASP,Geographic distance,Graph clustering,Intra- and inter-institutional collaborations,Modularity,Path relinking,Research specialty},
pages = {3121--3131},
primaryClass = {arxiv.org},
title = {{Community detection by modularity maximization using GRASP with path relinking}},
volume = {40},
year = {2013}
}
@article{Junttila,
author = {Junttila, Tommi and Kaski, Petteri},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Junttila, Kaski - Unknown - Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs Proceedings Vol. , No. (Societ.pdf:pdf},
language = {en},
title = {{Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs : Proceedings: Vol. , No. (Society for Industrial and Applied Mathematics)}},
url = {http://epubs.siam.org/doi/abs/10.1137/1.9781611972870.13}
}
@inproceedings{Satuluri2009,
abstract = {Algorithms based on simulating stochastic flows are a simple and natural solution for the problem of clustering graphs, but their widespread use has been hampered by their lack of scalability and fragmentation of output. In this article we present a multi-level algorithm for graph clustering using flows that delivers significant improvements in both quality and speed. The graph is first successively coarsened to a manageable size, and a small number of iterations of flow simulation is performed on the coarse graph. The graph is then successively refined, with flows from the previous graph used as initializations for brief flow simulations on each of the intermediate graphs. When we reach the final refined graph, the algorithm is run to convergence and the high-flow regions are clustered together, with regions without any flow forming the natural boundaries of the clusters. Extensive experimental results on several real and synthetic datasets demonstrate the effectiveness of our approach when compared to state-of-the-art algorithms.},
address = {New York, NY, USA},
author = {Satuluri, Venu and Parthasarathy, Srinivasan},
doi = {10.1145/1557019.1557101},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Satuluri, Parthasarathy - 2009 - Scalable Graph Clustering Using Stochastic Flows Applications to Community Discovery(4).pdf:pdf},
isbn = {978-1-60558-495-9},
keywords = {ALIRE,clustering,communities,graphs,networks},
mendeley-tags = {ALIRE,clustering,communities,graphs,networks},
pages = {737--746},
publisher = {ACM},
series = {KDD '09},
shorttitle = {Scalable Graph Clustering Using Stochastic Flows},
title = {{Scalable Graph Clustering Using Stochastic Flows: Applications to Community Discovery}},
url = {http://doi.acm.org/10.1145/1557019.1557101 http://dl.acm.org/ft\_gateway.cfm?id=1557101\&type=pdf},
year = {2009}
}
@inproceedings{Yang2013,
address = {New York, New York, USA},
author = {Yang, Jaewon and Leskovec, Jure},
booktitle = {Proceedings of the sixth ACM international conference on Web search and data mining - WSDM '13},
doi = {10.1145/2433396.2433471},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yang, Leskovec - 2013 - Overlapping community detection at scale(6).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yang, Leskovec - 2013 - Overlapping community detection at scale(7).pdf:pdf},
isbn = {9781450318693},
keywords = {matrix factorization,network communities,overlapping community detection},
month = feb,
pages = {587},
publisher = {ACM Press},
title = {{Overlapping community detection at scale}},
url = {http://dl.acm.org/citation.cfm?id=2433396.2433471},
year = {2013}
}
@article{DeVries2014,
abstract = {Online consumer behavior in general and online customer engagement with brands in particular, has become a major focus of research activity fuelled by the exponential increase of interactive functions of the internet and social media platforms and applications. Current research in this area is mostly hypothesis-driven and much debate about the concept of Customer Engagement and its related constructs remains existent in the literature. In this paper, we aim to propose a novel methodology for reverse engineering a consumer behavior model for online customer engagement, based on a computational and data-driven perspective. This methodology could be generalized and prove useful for future research in the fields of consumer behaviors using questionnaire data or studies investigating other types of human behaviors. The method we propose contains five main stages; symbolic regression analysis, graph building, community detection, evaluation of results and finally, investigation of directed cycles and common feedback loops. The 'communities' of questionnaire items that emerge from our community detection method form possible 'functional constructs' inferred from data rather than assumed from literature and theory. Our results show consistent partitioning of questionnaire items into such 'functional constructs' suggesting the method proposed here could be adopted as a new data-driven way of human behavior modeling.},
author = {de Vries, Natalie Jane and Carlson, Jamie and Moscato, Pablo},
doi = {10.1371/journal.pone.0102768},
editor = {Brody, James P.},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/de Vries, Carlson, Moscato - 2014 - A data-driven approach to reverse engineering customer engagement models towards functional construc.pdf:pdf},
issn = {1932-6203},
journal = {PloS one},
keywords = {Communications,Computational techniques,Empirical methods,Marketing,Mathematical modeling,Mathematics,Optimization,Physical sciences,Quantitative analysis,Questionnaires,Research Article,Research and analysis methods,Research design,Simulation and modeling,Social sciences,Sociology,Survey research,Surveys},
month = jan,
number = {7},
pages = {e102768},
pmid = {25036766},
publisher = {Public Library of Science},
title = {{A data-driven approach to reverse engineering customer engagement models: towards functional constructs.}},
url = {http://dx.plos.org/10.1371/journal.pone.0102768},
volume = {9},
year = {2014}
}
@misc{Trajanovski2014,
abstract = {Community structure is observed in many real-world networks, such as (online) social networks, where groups of friends of a certain person are often also friends of each other. Newman's modularity has been explored as an important quantitative metric for communities and clusters detection in networks. We present a new expressions and bounds for the modularity. These expressions reveal conditions for or properties of the maximum modularity of a network in both topological and spectral domains. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed in the past. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of partitions. The modularity depends on the chosen partitioning of the network into communities, which makes finding the specific partition that leads to the maximum modularity a hard problem. In this thesis, we prove that deciding whether a graph with a given number of links, number of communities, and modularity exists is NP-complete and subsequently propose a heuristic algorithm for generating random graphs with a given modularity and number of links with different topological properties. The generator can be used in the broad field of modeling and analyzing clustered social or organizational networks. We also propose a model which can randomly generate simple graphs which are line graphs of other simple graphs, employing an iterative merging procedure. These graphs possess interesting properties, for example, if the cliques are all of the same size, the assortativities of the line graphs in each step are close to 0, and the assortativities of the corresponding root graphs increases linearly from -1 to 0 with the steps of the nodal merging process. Due to their importance to society, communication systems, represented as complex networks, should be built and operated to withstand failures. We define robustness as the maintenance of functionality under node or link removal. In this context, the functionality is measured by several graph metrics. We study the robustness of both static and time-varying networks under node removal, considering random node failure, as well as targeted node attacks based on network centrality measures. In static networks, targeted and random failures have been studied in the literature; however, existing approaches tend to study random failure in terms of average-case behavior, giving no idea of how badly network performance can degrade purely by chance. Instead of considering average network performance under random failure, we compute the network performance probability density functions as functions of the fraction of nodes removed. We show that many centrality measures produce similar targeted attacks in both static and time-varying networks and that a combination of degree centrality and eigenvector centrality may be enough to evaluate worst-case behavior of static networks: even small subsets of highly connected nodes act as a bottleneck in the static or temporal information flow, becoming critical weak points of the entire system. We also study the robustness envelope and targeted attack responses of static networks that are rewired to have high and low degree assortativities, discovering that moderate assortativity increases confer more robustness against targeted attacks whilst moderate decreases confer more robustness against random uniform attacks. In time-varying randomly generated networks, where all the nodes have similar properties, we show that random errors and intelligent attacks exhibit similar behavior. However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously. Considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - a part of the network that can be enclosed by a given elementary figure of predetermined size - whose destruction would lead to the highest network disruption. We determine that the problem is polynomially solvable and propose appropriate algorithms. In addition, we consider region-aware network augmentation to decrease the impact of a regional failure. We subsequently address the region-disjoint paths problem, which asks for two paths with minimum total weight between a source and a destination that cannot both be cut by a single regional failure of a given diameter (unless that failure includes the source and the destination). We prove that deciding whether region-disjoint paths exist is NP-hard and propose a heuristic region-disjoint paths algorithm. Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. The first approach is a network adaptation, which is the interplay between disease dynamics on a network and the topology dynamics. A continuous-time adaptive Susceptible-Infectious-Susceptible (ASIS) model is introduced in order to investigate this interaction, where a susceptible node avoids infections by breaking its links to its infected neighbors while it enhances the connections with other susceptible nodes by creating links to them. When the initial topology of the network is a complete graph, an exact solution to the average metastable state fraction of infected nodes is derived without resorting to any mean-field approximation. A linear scaling law of the epidemic threshold as a function of the effective link-breaking rate is found. The metastable state topology shows high connectivity and low modularity in two cases: (i) a ``strongly adaptive'' region with very high effective spreading rate, and (ii) a ``weakly adaptive'' region with very low effective spreading rate. These two regions are separated from the other half-open elliptical-like regions of low connectivity and high modularity in a contour-line-like way. Our results indicate that the adaptation of the topology in response to disease dynamics suppresses the infection, while it promotes the network evolution towards a topology that exhibits assortative-mixing, modular structure and a binomial-like degree distribution. In the second approach, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. By assuming that each node in the network can decide to protect itself from infection at a constant cost, we model our system using a game theoretic framework. We find pure, mixed equilibria, and the Price of Anarchy (PoA) in several network topologies and propose algorithms to compute a pure equilibrium.},
author = {Trajanovski, S.},
doi = {10.4233/uuid:5560b786-32db-4ed1-9be8-ee8d6fc5e116},
file = {:home/gaumont/Documents/PhDThesis\_STrajanovski.pdf:pdf},
isbn = {http://repository.tudelft.nl/assets/uuid:5560b786-32db-4ed1-9be8-ee8d6fc5e116/PhDThesis\_STrajanovski.pdf},
keywords = {Complex Networks,Modularity,Network Robustness,Virus-Spread},
language = {en},
month = oct,
publisher = {TU Delft, Delft University of Technology},
title = {{Modular Structures, Robustness and Protection of Complex Networks: Theory, Complexity and Algorithms}},
url = {http://repository.tudelft.nl/view/ir/uuid:5560b786-32db-4ed1-9be8-ee8d6fc5e116/},
year = {2014}
}
@inproceedings{Pandit2011,
abstract = {The pattern of interactions between individuals in a population contains implicitly within them a remarkable amount of information. This information, if extracted, could be of significant importance in several realms such as containing the spread of disease, understanding information flow in social systems and predicting likely future interactions. A popular method of discovering structure in networks is through community detection which attempts to capture the extent to which that network is different from a random network. However, communities are not very well defined for time-varying networks. In this paper, we introduce the notion of spatio-temporal communities that attempts to capture the structure in spatial connections as well as temporal changes in a network. We illustrate the notion via several examples and list the challenges in effectively discovering spatio-temporal communities. For example, such communities are lost if the temporal interactions are aggregated in a single weighted network since the concurrency information is lost. We present an approach that first extracts concurrency information via node-clustering on each snapshot. Each node is then assigned a vector of community memberships over time, which is then used to group nodes into overlapping communities via recently introduced link clustering techniques. However we measure similarity (of nodes and edges) based on concurrence, i.e. when they existed, if they existed together. We call our approach the co-community algorithm. We validate our approach using several real-world data sets spanning multiple contexts.},
author = {Pandit, Saurav and Yang, Yang and Kawadia, Vikas and Sreenivasan, Sameet and Chawla, Nitesh V.},
booktitle = {Proceedings of the 2011 IEEE 1st International Network Science Workshop, NSW 2011},
doi = {10.1109/NSW.2011.6004643},
isbn = {9781457710490},
keywords = {community detection,contact graph Data mining,social network,temporal data},
pages = {173--179},
title = {{Detecting communities in time-evolving proximity networks}},
year = {2011}
}
@article{Viennet2014,
author = {Viennet},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Viennet - 2014 - Dynamique des communaut\'{e}s par pr\'{e}vision d’interactions dans les r\'{e}seaux sociaux(4).pdf:pdf},
title = {{Dynamique des communaut\'{e}s par pr\'{e}vision d’interactions dans les r\'{e}seaux sociaux}},
year = {2014}
}
@inproceedings{Shi2013,
abstract = {There is a surge of community detection study on complex network analysis in recent years, since communities often play important roles in network systems. However, many real networks have more complex overlapping community structures. This paper proposes a novel algorithm to discover overlapping communities. Different from conventional algorithms based on node clustering, the proposed algorithm is based on link clustering. Since links usually represent unique relations among nodes, the link clustering will discover groups of links that have the same characteristics. Thus nodes naturally belong to multiple communities. The algorithm applies genetic operation to cluster on links. An effective encoding schema is designed and the number of communities can be automatically determined. Experiments on both artificial networks and real networks validate the effectiveness and efficiency of the proposed algorithm. Crown Copyright ?? 2013 Published by Elsevier B.V. All rights reserved.},
author = {Shi, Chuan and Cai, Yanan and Fu, Di and Dong, Yuxiao and Wu, Bin},
booktitle = {Data and Knowledge Engineering},
doi = {10.1016/j.datak.2013.05.004},
file = {:home/gaumont/Documents/dke13-linkcommunity.pdf:pdf},
issn = {0169023X},
keywords = {Community detection,Genetic algorithm,Link community,Overlapping community},
pages = {394--404},
title = {{A link clustering based overlapping community detection algorithm}},
volume = {87},
year = {2013}
}
@article{Pfitzner2013,
abstract = {We study correlations in temporal networks and introduce the notion of betweenness preference. It allows to quantify to what extent paths, existing in time-aggregated representations of temporal networks, are actually realizable based on the sequence of interactions. We show that betweenness preference is present in empirical temporal network data and that it influences the length of shortest time-respecting paths. Using four different data sets, we further argue that neglecting betweenness preference leads to wrong conclusions about dynamical processes on temporal networks.},
archivePrefix = {arXiv},
arxivId = {1208.0588},
author = {Pfitzner, Ren\'{e} and Scholtes, Ingo and Garas, Antonios and Tessone, Claudio J. and Schweitzer, Frank},
doi = {10.1103/PhysRevLett.110.198701},
eprint = {1208.0588},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Pfitzner et al. - 2013 - Betweenness Preference Quantifying Correlations in the Topological Dynamics of Temporal Networks(3).pdf:pdf},
issn = {0031-9007},
journal = {Physical Review Letters},
month = may,
number = {19},
pages = {198701},
title = {{Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks}},
url = {http://arxiv.org/abs/1208.0588},
volume = {110},
year = {2013}
}
@article{Miyajima2014,
archivePrefix = {arXiv},
arxivId = {1412.0059},
author = {Miyajima, Kent and Sakuragawa, Takashi},
eprint = {1412.0059},
month = nov,
title = {{Continuous and robust clustering coefficients for weighted and directed networks}},
url = {http://arxiv.org/abs/1412.0059},
year = {2014}
}
@article{He,
annote = {transfomation de v\'{e}rit\'{e} de communaut\'{e} de liens},
author = {He, Chenglong and Ma, Hong and Kang, Shize and Cui, Ruifei},
doi = {10.1109/MILCOM.2014.149},
keywords = {Algorithm design and analysis,Clustering algorithms,Communities,Complex networks,Detection algorithms,Social network services,Time complexity,community detection,complex network,link community,link influence,overlapping community},
language = {English},
pages = {865--870},
publisher = {IEEE},
title = {{An Overlapping Community Detection Algorithm Based on Link Clustering in Complex Networks}},
url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6956870}
}
@article{Blondel2008a,
abstract = {We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks. .},
archivePrefix = {arXiv},
arxivId = {0803.0476},
author = {Blondel, Vincent D and Guillaume, Jean-Loup and Lambiotte, Renaud and Lefebvre, Etienne},
doi = {10.1088/1742-5468/2008/10/P10008},
eprint = {0803.0476},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Blondel et al. - 2008 - Fast unfolding of communities in large networks.pdf:pdf},
issn = {1742-5468},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
month = oct,
number = {10},
pages = {P10008},
title = {{Fast unfolding of communities in large networks}},
url = {http://arxiv.org/abs/0803.0476},
volume = {2008},
year = {2008}
}
@article{Liu2014,
author = {Liu, Wei and Pellegrini, Matteo and Wang, Xiaofan},
doi = {10.1038/srep05739},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Liu, Pellegrini, Wang - 2014 - Detecting Communities Based on Network Topology(4).pdf:pdf},
issn = {2045-2322},
journal = {Scientific Reports},
language = {en},
month = jul,
publisher = {Nature Publishing Group},
title = {{Detecting Communities Based on Network Topology}},
url = {http://www.nature.com/srep/2014/140718/srep05739/full/srep05739.html},
volume = {4},
year = {2014}
}
@article{Miyauchi2015,
abstract = {Identifying community structure in networks is an issue of particular interest in network science. The modularity introduced by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] is the most popular quality function for community detection in networks. In this study, we identify a problem in the concept of modularity and suggest a solution to overcome this problem. Specifically, we obtain a new quality function for community detection. We refer to the function as Z-modularity because it measures the Z-score of a given division with respect to the fraction of the number of edges within communities. Our theoretical analysis shows that Z-modularity mitigates the resolution limit of the original modularity in certain cases. Computational experiments using both artificial networks and well-known real-world networks demonstrate the validity and reliability of the proposed quality function.},
archivePrefix = {arXiv},
arxivId = {1501.01909},
author = {Miyauchi, Atsushi and Kawase, Yasushi},
eprint = {1501.01909},
month = jan,
pages = {8},
title = {{Z-score-based modularity for community detection in networks}},
url = {http://arxiv.org/abs/1501.01909},
year = {2015}
}
@article{Ruan2012,
abstract = {In this paper we discuss a very simple approach of combining content and link information in graph structures for the purpose of community discovery, a fundamental task in network analysis. Our approach hinges on the basic intuition that many networks contain noise in the link structure and that content information can help strengthen the community signal. This enables ones to eliminate the impact of noise (false positives and false negatives), which is particularly prevalent in online social networks and Web-scale information networks.   Specifically we introduce a measure of signal strength between two nodes in the network by fusing their link strength with content similarity. Link strength is estimated based on whether the link is likely (with high probability) to reside within a community. Content similarity is estimated through cosine similarity or Jaccard coefficient. We discuss a simple mechanism for fusing content and link similarity. We then present a biased edge sampling procedure which retains edges that are locally relevant for each graph node. The resulting backbone graph can be clustered using standard community discovery algorithms such as Metis and Markov clustering.   Through extensive experiments on multiple real-world datasets (Flickr, Wikipedia and CiteSeer) with varying sizes and characteristics, we demonstrate the effectiveness and efficiency of our methods over state-of-the-art learning and mining approaches several of which also attempt to combine link and content analysis for the purposes of community discovery. Specifically we always find a qualitative benefit when combining content with link analysis. Additionally our biased graph sampling approach realizes a quantitative benefit in that it is typically several orders of magnitude faster than competing approaches.},
archivePrefix = {arXiv},
arxivId = {1212.0146},
author = {Ruan, Yiye and Fuhry, David and Parthasarathy, Srinivasan},
eprint = {1212.0146},
month = dec,
title = {{Efficient Community Detection in Large Networks using Content and Links}},
url = {http://arxiv.org/abs/1212.0146},
year = {2012}
}
@article{Bassett2013,
abstract = {We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations (`optimization variance') and over randomizations of network structure (`randomization variance'). Because the modularity quality function typically has a large number of nearly-degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.},
author = {Bassett, Danielle S. and Porter, Mason A. and Wymbs, Nicholas F. and Grafton, Scott T. and Carlson, Jean M. and Mucha, Peter J.},
doi = {10.1063/1.4790830},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Bassett et al. - 2013 - Robust Detection of Dynamic Community Structure in Networks(3).pdf:pdf},
issn = {10541500},
journal = {Chaos: An Interdisciplinary Journal of Nonlinear Science},
keywords = {Brain network,Computer Science - Social and Information Networks,Condensed Matter - Disordered Systems and Neural N,Physics - Biological Physics,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,Quantitative Biology - Neurons and Cognition,Timed null model,tensor 3d,time community},
mendeley-tags = {Brain network,Computer Science - Social and Information Networks,Condensed Matter - Disordered Systems and Neural N,Physics - Biological Physics,Physics - Data Analysis- Statistics and Probabilit,Physics - Physics and Society,Quantitative Biology - Neurons and Cognition,Timed null model,tensor 3d,time community},
number = {1},
pages = {013142},
title = {{Robust Detection of Dynamic Community Structure in Networks}},
url = {http://arxiv.org/abs/1206.4358 http://www.arxiv.org/pdf/1206.4358.pdf},
volume = {23},
year = {2013}
}
@article{Cazabet2010,
abstract = {Community detection on networks is a well-known problem encountered in many fields, for which the existing algorithms are inefficient 1) at capturing overlaps in-between communities, 2) at detecting communities having disparities in size and density 3) at taking into account the networks' dynamics. In this paper, we propose a new algorithm (iLCD) for community detection using a radically new approach. Taking into account the dynamics of the network, it is designed for the detection of strongly overlapping communities. We first explain the main principles underlying the iLCD algorithm, introducing the two notions of intrinsic communities and longitudinal detection, and detail the algorithm. Then, we illustrate its efficiency in the case of a citation network, and then compare it with existing most efficient algorithms using a standard generator of community-based networks, the LFR benchmark.},
author = {Cazabet, R. and Amblard, F. and Hanachi, C.},
doi = {10.1109/SocialCom.2010.51},
isbn = {978-1-4244-8439-3},
journal = {Social Computing (SocialCom), 2010 IEEE Second International Conference on},
keywords = {Community detection,dynamic networks,social network analysis},
title = {{Detection of Overlapping Communities in Dynamical Social Networks}},
year = {2010}
}
@article{Sulo2010,
address = {New York, New York, USA},
author = {Sulo, Rajmonda and Berger-Wolf, Tanya and Grossman, Robert},
doi = {10.1145/1830252.1830269},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Sulo, Berger-Wolf, Grossman - 2010 - Meaningful selection of temporal resolution for dynamic networks(3).pdf:pdf},
isbn = {9781450302142},
journal = {Proceedings of the Eighth Workshop on Mining and Learning with Graphs - MLG '10},
pages = {127--136},
publisher = {ACM Press},
title = {{Meaningful selection of temporal resolution for dynamic networks}},
url = {http://portal.acm.org/citation.cfm?doid=1830252.1830269},
year = {2010}
}
@misc{Asur2009,
abstract = {Interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs from a static point of view. The study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. In this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. We use nonoverlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. We use these events to characterize complex behavioral patterns of individuals and communities over time. We show how semantic information can be incorporated to reason about community-behavior events. We also demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. Finally, we present a diffusion model for evolving networks, based on our framework.},
author = {Asur, Sitaram and Parthasarathy, Srinivasan and Ucar, Duygu},
booktitle = {ACM Transactions on Knowledge Discovery from Data},
doi = {10.1145/1631162.1631164},
isbn = {9781595936097},
issn = {15564681},
pages = {1--36},
title = {{An event-based framework for characterizing the evolutionary behavior of interaction graphs}},
volume = {3},
year = {2009}
}
@article{Crampes2014,
abstract = {Community detection using both graphs and social networks is the focus of many algorithms. Recent methods aimed at optimizing the so-called modularity function proceed by maximizing relations within communities while minimizing inter-community relations.   However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper, we introduce a new algorithm along with a function that takes an approximate solution and modifies it in order to reach an optimum. This reassignment function is considered a 'potential function' and becomes a necessary condition to asserting that the computed optimum is indeed a Nash Equilibrium. We also use this function to simultaneously show partitioning and overlapping communities, two detection and visualization modes of great value in revealing interesting features of a social network. Our approach is successfully illustrated through several experiments on either real unipartite, multipartite or directed graphs of medium and large-sized datasets.},
archivePrefix = {arXiv},
arxivId = {1406.6832},
author = {Crampes, Michel and Planti\'{e}, Michel},
eprint = {1406.6832},
month = jun,
title = {{Overlapping Community Detection Optimization and Nash Equilibrium}},
url = {http://arxiv.org/abs/1406.6832},
year = {2014}
}
@article{Lu2010,
abstract = {Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labelled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.},
archivePrefix = {arXiv},
arxivId = {1010.0725},
author = {Lu, Linyuan and Zhou, Tao},
eprint = {1010.0725},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lu, Zhou - 2010 - Link Prediction in Complex Networks A Survey(3).pdf:pdf},
month = oct,
pages = {44},
title = {{Link Prediction in Complex Networks: A Survey}},
url = {http://arxiv.org/abs/1010.0725},
year = {2010}
}
@article{Bianconi2014,
archivePrefix = {arXiv},
arxivId = {1407.1664},
author = {Bianconi, Ginestra and Darst, Richard K. and Iacovacci, Jacopo and Fortunato, Santo},
eprint = {1407.1664},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Bianconi et al. - 2014 - Triadic closure as a basic generating mechanism of the structure of complex networks.pdf:pdf},
month = jul,
title = {{Triadic closure as a basic generating mechanism of the structure of complex networks}},
url = {http://arxiv.org/abs/1407.1664},
year = {2014}
}
@article{Kovanen2013,
abstract = {Electronic communication records provide detailed information about temporal aspects of human interaction. Previous studies have shown that individuals' communication patterns have complex temporal structure, and that this structure has system-wide effects. In this paper we use mobile phone records to show that interaction patterns involving multiple individuals have non-trivial temporal structure that cannot be deduced from a network presentation where only interaction frequencies are taken into account. We apply a recently introduced method, temporal motifs, to identify interaction patterns in a temporal network where nodes have additional attributes such as gender and age. We then develop a null model that allows identifying differences between various types of nodes so that these differences are independent of the network based on interaction frequencies. We find gender-related differences in communication patters, and show the existence of temporal homophily, the tendency of similar individuals to participate in interaction patterns beyond what would be expected on the basis of the network structure alone. We also show that temporal patterns differ between dense and sparse parts of the network. Because this result is independent of edge weights, it can be considered as an extension of Granovetter's hypothesis to temporal networks.},
archivePrefix = {arXiv},
arxivId = {1302.2563},
author = {Kovanen, Lauri and Kaski, Kimmo and Kert\'{e}sz, J\'{a}nos and Saram\"{a}ki, Jari},
eprint = {1302.2563},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kovanen et al. - 2013 - Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks(3).pdf:pdf},
month = feb,
pages = {8},
title = {{Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks}},
url = {http://arxiv.org/abs/1302.2563},
year = {2013}
}
@article{Yu2013,
abstract = {Recently, complex networks have attracted considerable research attention. Community detection is an important problem in the field of complex networks and is useful in a variety of applications such as information propagation, link prediction, recommendation, and marketing. In this study, we focus on discovering overlapping community structures by using link partitions. We propose a Latent Dirichlet Allocation (LDA)-Based Link Partition (LBLP) method, which can find communities with an adjustable range of overlapping. This method employs the LDA model to detect link partitions, which can calculate the community belonging factor for each link. On the basis of this factor, link partitions with bridge links can be found efficiently. We validate the effectiveness of the proposed solution by using both real-world and synthesized networks. The experimental results demonstrate that the approach can find a meaningful and relevant link community structure.},
author = {Yu, L. and Wu, B. and Wang, B.},
doi = {10.1109/TST.2013.6574677},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yu, Wu, Wang - 2013 - LBLP link-clustering-based approach for overlapping community detection(3).pdf:pdf},
journal = {Tsinghua Science and Technology},
keywords = {Bridges,Clustering algorithms,Image edge detection,Inference algorithms,Overlapping community,Partitioning algorithms,communities,community detection,complex networks,latent Dirichlet allocation,link partition,overlapping,overlapping community detection},
mendeley-tags = {Bridges,Clustering algorithms,Image edge detection,Inference algorithms,Overlapping community,Partitioning algorithms,communities,community detection,complex networks,latent Dirichlet allocation,link partition,overlapping,overlapping community detection},
number = {4},
pages = {--},
shorttitle = {LBLP},
title = {{LBLP: link-clustering-based approach for overlapping community detection}},
url = {http://ieeexplore.ieee.org/ielx7/5971803/6574669/06574677.pdf?tp=\&arnumber=6574677\&isnumber=6574669},
volume = {18},
year = {2013}
}
@article{Liu2014a,
abstract = {There has been a surge of interest in community detection in homogeneous single-relational networks which contain only one type of nodes and edges. However, many real-world systems are naturally described as heterogeneous multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose a new method for detecting communities in such networks. Our method is based on optimizing the composite modularity, which is a new modularity proposed for evaluating partitions of a heterogeneous multi-relational network into communities. Our method is parameter-free, scalable, and suitable for various networks with general structure. We demonstrate that it outperforms the state-of-the-art techniques in detecting pre-planted communities in synthetic networks. Applied to a real-world Digg network, it successfully detects meaningful communities.},
archivePrefix = {arXiv},
arxivId = {1407.4989},
author = {Liu, Xin and Liu, Weichu and Murata, Tsuyoshi and Wakita, Ken},
eprint = {1407.4989},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Liu et al. - 2014 - A framework for community detection in heterogeneous multi-relational networks(3).pdf:pdf},
keywords = {bi-partit,k-parti,modularite},
mendeley-tags = {bi-partit,k-parti,modularite},
month = jul,
pages = {27},
title = {{A framework for community detection in heterogeneous multi-relational networks}},
url = {http://arxiv.org/abs/1407.4989},
year = {2014}
}
@book{Holme2013,
author = {Holme, Petter and Saram\"{a}ki, Jari},
isbn = {3642364608 9783642364600},
keywords = {EN\_COURS},
language = {English},
mendeley-tags = {EN\_COURS},
title = {{Temporal networks}},
year = {2013}
}
@misc{He2012,
abstract = {Discovery of communities in complex networks is a fundamental data analysis problem with applications in various domains. Most of the existing approaches have focused on discovering communities of nodes, while recent studies have shown great advantages and utilities of the knowledge of communities of links in networks. From this new perspective, we propose a link dynamics based algorithm, called UELC, for identifying link communities of networks. In UELC, the stochastic process of a link–node–link random walk is employed to unfold an embedded bipartition structure of links in a network. The local mixing properties of the Markov chain underlying the random walk are then utilized to extract two emerging link communities. Further, the random walk and the bipartitioning processes are wrapped in an iterative subdivision strategy to recursively identify link partitions that segregate the network links into multiple subdivisions. We evaluate the performance of the new method on synthetic benchmarks and demonstrate its utility on real-world networks. Our experimental results show that our method is highly effective for discovering link communities in complex networks. As a comparison, we also extend UELC to extracting communities of nodes, and show that it is effective for node community identification.},
annote = {Bipartition recursive},
archivePrefix = {arXiv},
arxivId = {1303.4699},
author = {He, Dongxiao and Liu, Dayou and Zhang, Weixiong and Jin, Di and Yang, Bo},
booktitle = {Journal of Statistical Mechanics: Theory and Experiment},
doi = {10.1088/1742-5468/2012/10/P10015},
eprint = {1303.4699},
file = {:home/gaumont/Documents/1303.4699v1.pdf:pdf},
issn = {1742-5468},
pages = {P10015},
title = {{Discovering link communities in complex networks by exploiting link dynamics}},
volume = {2012},
year = {2012}
}
@article{Nourbakhsh2014,
author = {Nourbakhsh, Farshad and {Rota Bul\`{o}}, Samuel and Pelillo, Marcello},
doi = {10.1007/s13042-014-0286-5},
issn = {1868-8071},
journal = {International Journal of Machine Learning and Cybernetics},
month = aug,
title = {{A matrix factorization approach to graph compression with partial information}},
url = {http://link.springer.com/10.1007/s13042-014-0286-5},
year = {2014}
}
@inproceedings{Lin2008,
address = {New York, New York, USA},
author = {Lin, Yu-Ru and Chi, Yun and Zhu, Shenghuo and Sundaram, Hari and Tseng, Belle L.},
booktitle = {Proceeding of the 17th international conference on World Wide Web - WWW '08},
doi = {10.1145/1367497.1367590},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lin et al. - 2008 - Facetnet A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks(3).pdf:pdf},
isbn = {9781605580852},
keywords = {community,community net,evolution,evolution net,non-negative matrix factorization,soft membership},
month = apr,
pages = {685},
publisher = {ACM Press},
title = {{Facetnet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks}},
url = {http://dl.acm.org/citation.cfm?id=1367497.1367590},
year = {2008}
}
@article{Zhang2014,
abstract = {Community detection in the social networks is one of the most important tasks of social computing. Highly relevant researches indicate that the social network generally contains both an overlapping and hierarchical structure. This paper introduces an efficient and functional community detection algorithm MOHCC, which can concurrently discover overlapping and hierarchical organization in complex networks. This algorithm first extracts all maximal cliques from the original complex network. Merges all extracted maximal cliques into a dendrogram by using the aggregative framework presented in MOHCC. Finally, it cuts through the dendrogram and obtains a network partition with maximum extended partition density. Experimental results utilizing computer-generated artificial networks and real-world social benchmark networks give satisfactory correspondence.},
author = {Zhang, Zhiwei and Wang, Zhenyu},
doi = {10.1016/j.physa.2014.11.023},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Community detection,Complex network,Maximal clique,Partition density},
month = nov,
title = {{Mining overlapping and hierarchical communities in complex networks}},
url = {http://www.sciencedirect.com/science/article/pii/S0378437114009741},
year = {2014}
}
@book{Muppalaneni2015,
address = {Singapore},
doi = {10.1007/978-981-287-338-5},
editor = {Muppalaneni, Naresh Babu and Gunjan, Vinit Kumar},
isbn = {978-981-287-337-8},
publisher = {Springer Singapore},
series = {SpringerBriefs in Applied Sciences and Technology},
title = {{Computational Intelligence Techniques for Comparative Genomics}},
url = {http://link.springer.com/10.1007/978-981-287-338-5},
year = {2015}
}
@book{Jain2015,
address = {New Delhi},
annote = {Application},
doi = {10.1007/978-81-322-2205-7},
editor = {Jain, Lakhmi C. and Behera, Himansu Sekhar and Mandal, Jyotsna Kumar and Mohapatra, Durga Prasad},
isbn = {978-81-322-2204-0},
publisher = {Springer India},
series = {Smart Innovation, Systems and Technologies},
title = {{Computational Intelligence in Data Mining - Volume 1}},
url = {http://link.springer.com/10.1007/978-81-322-2205-7},
volume = {31},
year = {2015}
}
@article{Wang2012,
author = {Wang, Qinna and Fleury, Eric and Aynaud, Thomas and Guillaume, Jean-Loup},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Wang et al. - 2012 - Communities in evolving networks definitions, detection and analysis techniques(3).pdf:pdf},
journal = {Dynamics of Time Varying Networks},
title = {{Communities in evolving networks: definitions, detection and analysis techniques}},
url = {http://hal.inria.fr/hal-00746195},
year = {2012}
}
@article{Li2014a,
author = {Li, Yongli and Wu, Chong and Wang, Zizheng},
doi = {10.1007/s11135-014-9996-8},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Li, Wu, Wang - 2014 - An information-theoretic approach for detecting communities in networks(4).pdf:pdf},
issn = {0033-5177},
journal = {Quality \& Quantity},
month = feb,
title = {{An information-theoretic approach for detecting communities in networks}},
url = {http://link.springer.com/10.1007/s11135-014-9996-8},
year = {2014}
}
@article{Esquivel2011,
abstract = {To better understand the overlapping modular organization of large networks with respect to flow, here we introduce the map equation for overlapping modules. In this information-theoretic framework, we use the correspondence between compression and regularity detection. The generalized map equation measures how well we can compress a description of flow in the network when we partition it into modules with possible overlaps. When we minimize the generalized map equation over overlapping network partitions, we detect modules that capture flow and determine which nodes at the boundaries between modules should be classified in multiple modules and to what degree. With a novel greedy search algorithm, we find that some networks, for example, the neural network of C. Elegans, are best described by modules dominated by hard boundaries, but that others, for example, the sparse European road network, have a highly overlapping modular organization.},
archivePrefix = {arXiv},
arxivId = {1105.0812},
author = {Esquivel, Alcides Viamontes and Rosvall, Martin},
doi = {10.1103/PhysRevX.1.021025},
eprint = {1105.0812},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Esquivel, Rosvall - 2011 - Compression of Flow Can Reveal Overlapping-Module Organization in Networks.pdf:pdf},
issn = {21603308},
journal = {Physical Review X},
keywords = {Complex Systems,Computational Physics,Interdisciplinary Physics},
pages = {1--11},
title = {{Compression of Flow Can Reveal Overlapping-Module Organization in Networks}},
volume = {1},
year = {2011}
}
@misc{Starnini2012a,
abstract = {Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various time scales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as a paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.},
archivePrefix = {arXiv},
arxivId = {1203.2477v2},
author = {Starnini, Michele and Baronchelli, Andrea and Barrat, Alain and Pastor-Satorras, Romualdo},
booktitle = {Physical Review E},
doi = {10.1103/PhysRevE.85.056115},
eprint = {1203.2477v2},
issn = {1539-3755},
title = {{Random walks on temporal networks}},
volume = {85},
year = {2012}
}
@article{Havemann2015,
abstract = {We propose an algorithm for detecting communities of links in networks which uses local information, is based on a new evaluation function, and allows for pervasive overlaps of communities. The complexity of the clustering task requires the application of a memetic algorithm that combines probabilistic evolutionary strategies with deterministic local searches. In Part 2 we will present results of experiments with a large citation network of astrophysical papers.},
archivePrefix = {arXiv},
arxivId = {1501.05139},
author = {Havemann, Frank and Gl\"{a}ser, Jochen and Heinz, Michael},
eprint = {1501.05139},
month = jan,
pages = {11},
title = {{Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method}},
url = {http://arxiv.org/abs/1501.05139},
year = {2015}
}
@article{Casteigts2010,
abstract = {The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.},
archivePrefix = {arXiv},
arxivId = {1012.0009},
author = {Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola},
eprint = {1012.0009},
month = nov,
title = {{Time-Varying Graphs and Dynamic Networks}},
url = {http://arxiv.org/abs/1012.0009},
year = {2010}
}
@inproceedings{MacKer2012,
abstract = {This work presents applied research using spectral graph partitioning to examine potential community structures in evolving graphs. In our early experiments, evolving graphs represent time varying models of mobile wireless communication networks but they could also represent more abstract architectural representations such as middleware topologies or social network dynamics. While in its technical infancy, mobile network community analysis is an important capability in network planning, management, and adaptation strategies. We first present some discussion and technical background required to describe the analytical components and dynamic network modeling techniques. A set of mobile network scenarios are then described and applied to demonstrate the use of the dynamic spectral partitioning methods. We also develop and present a potential aid to dynamically establish partition set size and introduce a heuristic metric for partitioning quality. Our dynamic network experiments are represented by a series of evolving weighted graphs with dynamic attribute data that we plan to use in future work to represent network neighbor quality effects or other metrics as deemed appropriate to the scenario. We conclude by reviewing results and discussing future work.},
author = {MacKer, Joseph P. and Claypool, David J.},
booktitle = {Proceedings - IEEE Military Communications Conference MILCOM},
doi = {10.1109/MILCOM.2012.6415614},
isbn = {9781467317290},
title = {{Dynamic communities in evolving network graphs}},
year = {2012}
}
@article{Jacobs2014,
annote = {Random model},
archivePrefix = {arXiv},
arxivId = {1411.4070},
author = {Jacobs, Abigail Z. and Clauset, Aaron},
eprint = {1411.4070},
month = nov,
title = {{A unified view of generative models for networks: models, methods, opportunities, and challenges}},
url = {http://arxiv.org/abs/1411.4070},
year = {2014}
}
@misc{Ball,
author = {Ball, Brian Joseph},
file = {:home/gaumont/Documents/briball\_1.pdf:pdf},
keywords = {Block modelling},
title = {{Blockmodeling techniques for complex networks}},
url = {http://deepblue.lib.umich.edu/bitstream/handle/2027.42/108855/briball\_1.pdf?sequence=1\&isAllowed=y},
urldate = {2014-10-21}
}
@article{Rosvall2008,
abstract = {To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network-including physics, chemistry, molecular biology, and medicine-information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.},
author = {Rosvall, Martin and Bergstrom, Carl T},
doi = {10.1073/pnas.0706851105},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Rosvall, Bergstrom - 2008 - Maps of random walks on complex networks reveal community structure(6).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Rosvall, Bergstrom - 2008 - Maps of random walks on complex networks reveal community structure(7).pdf:pdf},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
keywords = {Bibliometrics,Biomedical Research,Biomedical Research: instrumentation,Biomedical Research: methods,Biomedical Research: statistics \& numerical data,Community detection,Information Theory,Markov Chains,Periodicals as Topic,Science,Science: instrumentation,Science: methods,Science: statistics \& numerical data,infomap},
mendeley-tags = {Community detection,infomap},
month = jan,
number = {4},
pages = {1118--23},
pmid = {18216267},
title = {{Maps of random walks on complex networks reveal community structure.}},
url = {http://www.pnas.org/content/105/4/1118.abstract},
volume = {105},
year = {2008}
}
@article{Lancichinetti2009b,
abstract = {Many complex networks display a mesoscopic structure with groups of nodes sharing many links with the other nodes in their group and comparatively few with nodes of different groups. This feature is known as community structure and encodes precious information about the organization and the function of the nodes. Many algorithms have been proposed but it is not yet clear how they should be tested. Recently we have proposed a general class of undirected and unweighted benchmark graphs, with heterogeneous distributions of node degree and community size. An increasing attention has been recently devoted to develop algorithms able to consider the direction and the weight of the links, which require suitable benchmark graphs for testing. In this paper we extend the basic ideas behind our previous benchmark to generate directed and weighted networks with built-in community structure. We also consider the possibility that nodes belong to more communities, a feature occurring in real systems, such as social networks. As a practical application, we show how modularity optimization performs on our benchmark.},
archivePrefix = {arXiv},
arxivId = {0904.3940},
author = {Lancichinetti, Andrea and Fortunato, Santo},
doi = {10.1103/PhysRevE.80.016118},
eprint = {0904.3940},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato - 2009 - Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping.pdf:pdf},
issn = {1539-3755},
journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
keywords = {Benchmark},
mendeley-tags = {Benchmark},
pages = {016118},
pmid = {19658785},
title = {{Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.}},
volume = {80},
year = {2009}
}
@article{Hric2014a,
archivePrefix = {arXiv},
arxivId = {1406.0146},
author = {Hric, Darko and Darst, Richard K. and Fortunato, Santo},
doi = {10.1103/PhysRevE.90.062805},
eprint = {1406.0146},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Hric, Darst, Fortunato - 2014 - Community detection in networks structural clusters versus ground truth(4).pdf:pdf},
issn = {1539-3755},
journal = {Physical Review E},
number = {6},
pages = {062805},
title = {{Community detection in networks: Structural communities versus ground truth}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.90.062805},
volume = {90},
year = {2014}
}
@inproceedings{Gaumont2014,
abstract = {La recherche de communaut\'{e}s chevauchantes est un enjeu important pour l'analyse des r\'{e}seaux complexes. Une piste souvent envisag\'{e}e est la recherche d'un partitionnement des ar\^{e}tes du graphe. L'\'{e}valuation de cette d\'{e}composition tient cependant rarement compte du fait que les communaut\'{e}s recherch\'{e}es correspondent \`{a} des groupes d'ar\^{e}tes. Nous discutons dans ce papier l'utilisation de nouveaux crit\`{e}res pouvant r\'{e}pondre \`{a} ce probl\`{e}me. Nous proposons de comparer le nombre de sommets incidents \`{a} un groupe d'ar\^{e}tes au nombre attendu dans un graphe al\'{e}atoire. Un optimum local de la mesure d\'{e}riv\'{e}e de ce concept peut \^{e}tre obtenu par un algorithme glouton. Nous pr\'{e}sentons les premiers r\'{e}sultats obtenus \`{a} travers une analyse de la mesure et des tests empiriques.},
author = {Gaumont, No\'{e} and Queyroi, Fran\c{c}ois},
booktitle = {ALGOTEL 2014 -- 16\`{e}mes Rencontres Francophones sur les Aspects Algorithmiques des T\'{e}l\'{e}communications},
language = {fr},
pages = {1--4},
title = {{Partitionnement des Liens d'un Graphe : Crit\`{e}res et Mesures}},
url = {https://hal.archives-ouvertes.fr/hal-00986216},
year = {2014}
}
@inproceedings{Gaumont2016b,
abstract = {.},
author = {Gaumont, No\'{e}},
booktitle = {ALGOTEL in submission},
language = {fr},
title = {{Trouver des séquences de contacts pertinentes dans un flot de liens}},
year = {2016}
}

@inproceedings{Gaumont2016c,
abstract = {.},
author = {Gaumont, No\'{e}},
booktitle = {Workshop Dynamics On and Of Networks, in submission},
title = {{LinkStreamViz: a drawing tool for link streams}},
year = {2016}
}



@article{Kolda2009,
abstract = {This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or N-way array. Decompositions of higher-order tensors (i.e., N-way arrays with \$N \backslash geq 3\$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.},
annote = {Tensor factorisation},
author = {Kolda, Tamara G. and Bader, Brett W.},
doi = {10.1137/07070111X},
issn = {0036-1445},
journal = {SIAM Review},
keywords = {15A69,65F99,canonical decomposition (CANDECOMP),higher-order principal components analysis (Tucker,higher-order singular value decomposition (HOSVD),multilinear algebra,multiway arrays,parallel factors (PARAFAC),tensor decompositions},
language = {en},
month = aug,
number = {3},
pages = {455--500},
publisher = {Society for Industrial and Applied Mathematics},
title = {{Tensor Decompositions and Applications}},
url = {http://epubs.siam.org/doi/abs/10.1137/07070111X},
volume = {51},
year = {2009}
}
@article{Huang2014,
abstract = {It is a classic topic of social network analysis to evaluate the importance of nodes and identify the node that takes on the role of core or bridge in a network. Because a single indicator is not sufficient to analyze multiple characteristics of a node, it is a natural solution to apply multiple indicators that should be selected carefully. An intuitive idea is to select some indicators with weak correlations to efficiently assess different characteristics of a node. However, this paper shows that it is much better to select the indicators with strong correlations. Because indicator correlation is based on the statistical analysis of a large number of nodes, the particularity of an important node will be outlined if its indicator relationship doesn't comply with the statistical correlation. Therefore, the paper selects the multiple indicators including degree, ego-betweenness centrality and eigenvector centrality to evaluate the importance and the role of a node. The importance of a node is equal to the normalized sum of its three indicators. A candidate for core or bridge is selected from the great degree nodes or the nodes with great ego-betweenness centrality respectively. Then, the role of a candidate is determined according to the difference between its indicators' relationship with the statistical correlation of the overall network. Based on 18 real networks and 3 kinds of model networks, the experimental results show that the proposed methods perform quite well in evaluating the importance of nodes and in identifying the node role.},
annote = {Mesure sommets},
author = {Huang, Shaobin and Lv, Tianyang and Zhang, Xizhe and Yang, Yange and Zheng, Weimin and Wen, Chao},
doi = {10.1371/journal.pone.0103733},
editor = {Csermely, Peter},
file = {:home/gaumont/Documents/journal.pone.0103733.pdf:pdf},
issn = {1932-6203},
journal = {PloS one},
keywords = {Algorithms,Applied mathematics,Computational sociology,Computer and information sciences,Computer modeling,Computing methods,Mathematical computing,Mathematics,Network analysis,Physical sciences,Research Article,Social networks,Social research,Social sciences,Social systems,Sociology},
month = jan,
number = {8},
pages = {e103733},
pmid = {25089823},
publisher = {Public Library of Science},
title = {{Identifying Node Role in Social Network Based on Multiple Indicators.}},
url = {http://dx.plos.org/10.1371/journal.pone.0103733},
volume = {9},
year = {2014}
}
@article{Queyroi2014,
author = {Queyroi, Fran\c{c}ois},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Queyroi - 2014 - Time-Varying Graphs Analysis via ∆ -duplication(4).pdf:pdf},
pages = {2--6},
title = {{Time-Varying Graphs Analysis via ∆ -duplication}},
year = {2014}
}
@article{Lin2014,
abstract = {With the rapid development of Web 2.0 and the rise of online social networks, finding community structures from user data has become a hot topic in network analysis. Although research achievements are numerous at present, most of these achievements cannot be adopted in large-scale social networks because of heavy computation. Previous studies have shown that label propagation is an efficient means to detect communities in social networks and is easy to implement; however, some drawbacks, such as low accuracy, high randomness, and the formation of a “monster” community, have been found. In this study, we propose an efficient community detection method based on the label propagation algorithm (LPA) with community kernel (CK-LPA). We assign a corresponding weight to each node according to node importance in the whole network and update node labels in sequence based on weight. Then, we discuss the composition of weights, the label updating strategy, the label propagation strategy, and the convergence conditions. Compared with the primitive LPA, existing drawbacks are solved by CK-LPA. Experiments and benchmarks reveal that our proposed method sustains nearly linear time complexity and exhibits significant improvements in the quality aspect of static community detection. Hence, the algorithm can be applied in large-scale social networks.},
author = {Lin, Zhen and Zheng, Xiaolin and Xin, Nan and Chen, Deren},
doi = {10.1016/j.physa.2014.09.023},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lin et al. - 2014 - CK-LPA Efficient community detection algorithm based on label propagation with community kernel.pdf:pdf},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {Community detection,Community kernel,Graph mining,Label propagation,Online social network},
month = dec,
pages = {386--399},
title = {{CK-LPA: Efficient community detection algorithm based on label propagation with community kernel}},
url = {http://www.sciencedirect.com/science/article/pii/S037843711400781X},
volume = {416},
year = {2014}
}
@article{Prat-Perez2012,
archivePrefix = {arXiv},
arxivId = {1207.6269},
author = {Prat-P\'{e}rez, Arnau and Dominguez-Sal, David and Brunat, Josep M. and Larriba-Pey, Josep-Lluis},
eprint = {1207.6269},
file = {:home/gaumont/Documents/1207.6269v1.pdf:pdf},
month = jul,
title = {{Shaping Communities out of Triangles}},
url = {http://arxiv.org/abs/1207.6269},
year = {2012}
}
@article{Evans2009,
abstract = {In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm that produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this.},
archivePrefix = {arXiv},
arxivId = {0903.2181},
author = {Evans, T. S. and Lambiotte, Renaud},
doi = {10.1103/PhysRevE.80.016105},
eprint = {0903.2181},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Evans, Lambiotte - 2009 - Line graphs, link partitions, and overlapping communities(4).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Evans, Lambiotte - 2009 - Line graphs, link partitions, and overlapping communities(3).html:html;:home/gaumont/Documents/link.pdf:pdf},
isbn = {1539-3755 (Print)$\backslash$r1539-3755 (Linking)},
issn = {1539-3755},
journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
keywords = {ALIRE,Link,link partition},
mendeley-tags = {ALIRE,Link,link partition},
month = jul,
number = {1},
pages = {016105},
pmid = {19658772},
title = {{Line graphs, link partitions, and overlapping communities.}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.80.016105 http://pre.aps.org/abstract/PRE/v80/i1/e016105 http://pre.aps.org/pdf/PRE/v80/i1/e016105},
volume = {80},
year = {2009}
}
@article{Pan2014,
abstract = {Complex networks describe a wide range of systems in nature and society. To understand complex networks, it is crucial to investigate their community structure. In this paper, we develop an online community detection algorithm with linear time complexity for large complex networks. Our algorithm processes a network edge by edge in the order that the network is fed to the algorithm. If a new edge is added, it just updates the existing community structure in constant time, and does not need to re-compute the whole network. Therefore, it can efficiently process large networks in real time. Our algorithm optimizes expected modularity instead of modularity at each step to avoid poor performance. The experiments are carried out using 11 public data sets, and are measured by two criteria, modularity and NMI (Normalized Mutual Information). The results show that our algorithm's running time is less than the commonly used Louvain algorithm while it gives competitive performance.},
author = {Pan, Gang and Zhang, Wangsheng and Wu, Zhaohui and Li, Shijian},
doi = {10.1371/journal.pone.0102799},
editor = {Moreno, Yamir},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Pan et al. - 2014 - Online Community Detection for Large Complex Networks(3).pdf:pdf},
issn = {1932-6203},
journal = {PLoS ONE},
keywords = {Algorithms,Applied mathematics,Biology and life sciences,Community ecology,Community structure,Computational biology,Computer and information sciences,Computer modeling,Computerized simulations,Databases,Ecology,Ecology and environmental sciences,Genetic networks,Genetics,Genome analysis,Genomics,Information technology,Mathematics,Network analysis,Physical sciences,Research Article,Social networks,Social sciences,Sociology},
month = jul,
number = {7},
pages = {e102799},
publisher = {Public Library of Science},
title = {{Online Community Detection for Large Complex Networks}},
url = {http://dx.plos.org/10.1371/journal.pone.0102799},
volume = {9},
year = {2014}
}
@inproceedings{Yoo2014,
address = {New York, New York, USA},
author = {Yoo, Boyoung and Chen, Huili and Faisal, Fazle E. and Milenkovi\'{c}, Tijana},
booktitle = {Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics - BCB '14},
doi = {10.1145/2649387.2649426},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yoo et al. - 2014 - Improving identification of key players in aging via network de-noising.pdf:pdf},
isbn = {9781450328944},
keywords = {Link prediction,aging,biological networks,link prediction,network de-noising,protein function prediction},
mendeley-tags = {Link prediction},
month = sep,
pages = {164--173},
publisher = {ACM Press},
title = {{Improving identification of key players in aging via network de-noising}},
url = {http://dl.acm.org/citation.cfm?id=2649387.2649426},
year = {2014}
}
@article{Karsai2014,
abstract = {In most social and information systems the activity of agents generates rapidly evolving time-varying networks. The temporal variation in networks' connectivity patterns and the ongoing dynamic processes are usually coupled in ways that still challenge our mathematical or computational modelling. Here we analyse a mobile call dataset and find a simple statistical law that characterize the temporal evolution of users' egocentric networks. We encode this observation in a reinforcement process defining a time-varying network model that exhibits the emergence of strong and weak ties. We study the effect of time-varying and heterogeneous interactions on the classic rumour spreading model in both synthetic, and real-world networks. We observe that strong ties severely inhibit information diffusion by confining the spreading process among agents with recurrent communication patterns. This provides the counterintuitive evidence that strong ties may have a negative role in the spreading of information across networks.},
archivePrefix = {arXiv},
arxivId = {1303.5966},
author = {Karsai, M\'{a}rton and Perra, Nicola and Vespignani, Alessandro},
doi = {10.1038/srep04001},
eprint = {1303.5966},
issn = {2045-2322},
journal = {Scientific reports},
month = jan,
pages = {4001},
pmid = {24510159},
title = {{Time varying networks and the weakness of strong ties.}},
url = {http://arxiv.org/abs/1303.5966},
volume = {4},
year = {2014}
}
@article{Leger2015,
author = {Leger, Jean-Benoist and Daudin, Jean-Jacques and Vacher, Corinne},
doi = {10.1111/2041-210X.12334},
issn = {2041210X},
journal = {Methods in Ecology and Evolution},
month = jan,
pages = {n/a--n/a},
title = {{Clustering methods differ in their ability to detect patterns in ecological networks}},
url = {http://doi.wiley.com/10.1111/2041-210X.12334},
year = {2015}
}
@article{Hu2014,
abstract = {Along with the development of internet, our personal online social networks become bigger and more jumbled than before, and it is necessary to provide a good way to organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g., ‘list’ on Facebook and Twitter), but it is laborious. The problem of social circles identifying is thus posed on a user’s ego network, while there are currently few efficient as well as effective methods to identify user’s social circles. In this paper, we propose a new method, named enhanced link clustering, for social circles identifying on ego networks. The proposed method integrates node profile and network structure by constructing an edge profile for each edge. Utilization of both node profile and network structure information makes the proposed method more effective. Taking edge similarity instead of node similarity to discriminate nodes into different circles allows us to detect overlapping circles. Moreover, we observe that nodes in one circle appear transitive similarity and some nodes are only densely connected, or share common properties. These observations make the process of edge clustering efficient. Experiments on several real datasets demonstrate that our method is much faster, and also more effective compared with maximization likelihood-like method, which has been proved to dominate most methods.},
author = {Hu, Yanmei and Yang, Bo},
doi = {10.1016/j.knosys.2014.10.006},
issn = {09507051},
journal = {Knowledge-Based Systems},
keywords = {Edge clustering,Ego network,Node profile,Online social network,Social circles identifying},
month = oct,
title = {{Enhanced link clustering with observations on ground truth to discover social circles}},
url = {http://www.sciencedirect.com/science/article/pii/S0950705114003736},
year = {2014}
}
@article{Liao2014,
archivePrefix = {arXiv},
arxivId = {1409.8481},
author = {Liao, Hao and Zeng, An},
eprint = {1409.8481},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Liao, Zeng - 2014 - Reconstructing propagation networks with temporal similarity metrics.pdf:pdf},
month = sep,
title = {{Reconstructing propagation networks with temporal similarity metrics}},
url = {http://arxiv.org/abs/1409.8481v1},
year = {2014}
}
@article{Coscia2012,
abstract = {Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighborhood, using a label propagation algorithm; finally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a limited time complexity, so that it can be used on web-scale real networks.},
archivePrefix = {arXiv},
arxivId = {1206.0629},
author = {Coscia, Michele and Rossetti, G},
doi = {10.1145/2339530.2339630},
eprint = {1206.0629},
isbn = {9781450314626},
journal = {\ldots discovery and data mining},
pages = {615--623},
title = {{Demon: a local-first discovery method for overlapping communities}},
url = {http://dl.acm.org/citation.cfm?id=2339630},
year = {2012}
}
@inproceedings{Pan2011a,
abstract = {Detecting communities from networks has been given great attention these years. The traditional approaches were always focusing on the node community, while some recent studies have shown great advantage of link community approach which partitions links instead of nodes into communities. We proposed a novel algorithm LBLC (local based link community) to detect link communities in the network based on local information. A local link community can be detected by maximizing a local link fitness function from a seed link, which was ranked by another algorithm previously. The proposed LBLC algorithm has been tested on both synthetic and real world networks, and it has been compared with other link community detecting algorithm. The experimental results showed LBLC achieves significant improvement on link community structure.},
author = {Pan, Lei and Wang, Chongjun and Xie, Junyuan and Liu, Meilin},
booktitle = {Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI},
doi = {10.1109/ICTAI.2011.140},
file = {:home/gaumont/Documents/chp\%3A10.1007\%2F978-3-642-31900-6\_36.pdf:pdf},
isbn = {9780769545967},
issn = {10823409},
keywords = {Community detection,Link community,Local community},
pages = {884--886},
title = {{Detecting link communities based on local approach}},
year = {2011}
}
@book{MohammadAlHasan2011,
address = {Boston, MA},
author = {{Mohammad Al Hasan}, Mohammed J. Zaki},
doi = {10.1007/978-1-4419-8462-3},
editor = {Aggarwal, Charu C.},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Mohammad Al Hasan - 2011 - Social Network Data Analytics(4).pdf:pdf},
isbn = {978-1-4419-8461-6},
pages = {243 -- 275},
publisher = {Springer US},
title = {{Social Network Data Analytics}},
url = {http://www.springerlink.com/index/10.1007/978-1-4419-8462-3},
year = {2011}
}
@article{Rosvall2014,
author = {Rosvall, Martin and Esquivel, Alcides Viamontes and Lancichinetti, Andrea and West, Jevin D. and Lambiotte, Renaud},
doi = {10.1038/ncomms5630},
file = {:home/gaumont/Documents/1305.4807v4.pdf:pdf},
issn = {2041-1723},
journal = {Nature Communications},
language = {en},
month = aug,
publisher = {Nature Publishing Group},
title = {{Memory in network flows and its effects on spreading dynamics and community detection}},
url = {http://www.nature.com/ncomms/2014/140811/ncomms5630/full/ncomms5630.html},
volume = {5},
year = {2014}
}
@article{Fan2014,
abstract = {A general \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn1.gif] \{\$(k,l)\$\} clique community of a network, which consists of adjacent k -cliques sharing at least l vertices with \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn2.gif] \{\$k-1\backslash ge l\backslash ge1\$\} , is introduced. With the emergence of a giant \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn3.gif] \{\$(k,l)\$\} clique community in the network, there is a \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn4.gif] \{\$(k,l)\$\} clique percolation. Using the largest size jump $\Delta$ of the largest clique community during network evolution and the corresponding evolution step T c , we study the general \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn5.gif] \{\$(k,l)\$\} clique percolation of the Erdős-R\'{e}nyi network. We investigate the averages of $\Delta$ and T c and their fluctuations for different network size N . The clique percolation can be identified by the power-law finite-size effects of the averages and root mean squares of fluctuation. The finite-size scaling distribution functions of fluctuations are calculated. The universality class of the \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn6.gif] \{\$(k,l)\$\} clique percolation is characterized by the critical exponents of power-law finite-size effects. Using Monte Carlo simulations, we find that the Erdős-R\'{e}nyi network experiences a series of \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn7.gif] \{\$(k,l)\$\} clique percolation with \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn8.gif] \{\$(k,l)=(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1)\$\} . We find that the critical exponents and therefore the universality class of the \#\#IMG\#\# [http://ej.iop.org/images/0295-5075/107/2/28005/epl16408ieqn9.gif] \{\$(k,l)\$\} clique percolation depend on clique connection index l , but are independent of clique size k .},
author = {Fan, Jingfang and Chen, Xiaosong},
doi = {10.1209/0295-5075/107/28005},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Fan, Chen - 2014 - General clique percolation in random networks(4).pdf:pdf},
issn = {0295-5075},
journal = {EPL (Europhysics Letters)},
month = jul,
number = {2},
pages = {28005},
title = {{General clique percolation in random networks}},
url = {http://stacks.iop.org/0295-5075/107/i=2/a=28005},
volume = {107},
year = {2014}
}
@article{Good2010,
abstract = {Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the resolution limit phenomenon for modularity maximization. Second, we show that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum. Third, we derive the limiting behavior of the maximum modularity Q\_max for one model of infinitely modular networks, showing that it depends strongly both on the size of the network and on the number of modules it contains. Finally, using three real-world metabolic networks as examples, we show that the degenerate solutions can fundamentally disagree on many, but not all, partition properties such as the composition of the largest modules and the distribution of module sizes. These results imply that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts. They also explain why many heuristics are often successful at finding high-scoring partitions in practice and why different heuristics can disagree on the modular structure of the same network. We conclude by discussing avenues for mitigating some of these behaviors, such as combining information from many degenerate solutions or using generative models.},
annote = {Comportement de la modularit\'{e}},
archivePrefix = {arXiv},
arxivId = {0910.0165},
author = {Good, Benjamin H. and de Montjoye, Yves-Alexandre and Clauset, Aaron},
doi = {10.1103/PhysRevE.81.046106},
eprint = {0910.0165},
file = {:home/gaumont/Documents/0910.0165v2.pdf:pdf},
issn = {1539-3755},
journal = {Physical Review E},
month = apr,
number = {4},
pages = {046106},
title = {{Performance of modularity maximization in practical contexts}},
url = {http://arxiv.org/abs/0910.0165},
volume = {81},
year = {2010}
}
@book{Li2012,
address = {Berlin, Heidelberg},
doi = {10.1007/978-3-642-31900-6},
editor = {Li, Tianrui and Nguyen, Hung Son and Wang, Guoyin and Grzymala-Busse, Jerzy and Janicki, Ryszard and Hassanien, Aboul Ella and Yu, Hong},
file = {:home/gaumont/Documents/chp\%3A10.1007\%2F978-3-642-31900-6\_36.pdf:pdf},
isbn = {978-3-642-31899-3},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{Rough Sets and Knowledge Technology}},
url = {http://www.springerlink.com/index/10.1007/978-3-642-31900-6},
volume = {7414},
year = {2012}
}
@article{Goldberg2010,
abstract = {The typical task of unsupervised learning is to organize data, for example into clusters, typically disjoint clusters (eg. the K-means algorithm). One would expect (for example) a clustering of books into topics to present overlapping clusters. The situation is even more so in social networks, a source of ever increasing data. Finding the groups or communities in social networks based on interactions between individuals (a measure of similarity) is an unsupervised learning task; and, groups overlap - an individual can be a chess player and a violin player, in which case he would interact with members of both these groups. The problem we address is not that of finding the overlapping clusters, but of comparing two sets of overlapping clusters. Such a task is the basis for comparing two different clusterings, which is important for comparing algorithms with each other or with a ground truth. From the social network point of view, we are particularly interested in quantifying social group evolution - how much the social group structure of a social network changed - by comparing the set of groups at consecutive time intervals. There is significant prior work on comparing sets of disjoint clusters (partitions). When overlap is allowed, the problem becomes considerably more complex owing to the possibility of degeneracies, which we illustrate through examples. We describe three novel definitions of the distance between collections of potentially overlapping sets, and present algorithms for computing those distances. We test our algorithms on diverse data sets: collections composed from social groups in Twitter, Blogosphere and Enron Email data.},
author = {Goldberg, M.K. and Hayvanovych, M. and Magdon-Ismail, M.},
doi = {10.1109/SocialCom.2010.50},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Goldberg, Hayvanovych, Magdon-Ismail - 2010 - Measuring Similarity between Sets of Overlapping Clusters(4).pdf:pdf},
isbn = {978-1-4244-8439-3},
journal = {Social Computing (SocialCom), 2010 IEEE Second International Conference on},
title = {{Measuring Similarity between Sets of Overlapping Clusters}},
year = {2010}
}
@article{Kim2012,
abstract = {Many networks are dynamic in that their topology changes rapidly—on the same time scale as the communications of interest between network nodes. Examples are the human contact networks involved in the transmission of disease, ad hoc radio networks between moving vehicles, and the transactions between principals in a market. While we have good models of static networks, so far these have been lacking for the dynamic case. In this paper we present a simple but powerful model, the time-ordered graph, which reduces a dynamic network to a static network with directed flows. This enables us to extend network properties such as vertex degree, closeness, and betweenness centrality metrics in a very natural way to the dynamic case. We then demonstrate how our model applies to a number of interesting edge cases, such as where the network connectivity depends on a small number of highly mobile vertices or edges, and show that our centrality definition allows us to track the evolution of connectivity. Finally we apply our model and techniques to two real-world dynamic graphs of human contact networks and then discuss the implication of temporal centrality metrics in the real world.},
author = {Kim, Hyoungshick and Anderson, Ross},
doi = {10.1103/PhysRevE.85.026107},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kim, Anderson - 2012 - Temporal node centrality in complex networks(4).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Kim, Anderson - 2012 - Temporal node centrality in complex networks(4).html:html},
journal = {Physical Review E},
month = feb,
number = {2},
pages = {026107},
title = {{Temporal node centrality in complex networks}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.85.026107 http://pre.aps.org/abstract/PRE/v85/i2/e026107 http://pre.aps.org/pdf/PRE/v85/i2/e026107},
volume = {85},
year = {2012}
}
@article{Lancichinetti2011,
abstract = {Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.},
author = {Lancichinetti, Andrea and Fortunato, Santo},
doi = {10.1103/PhysRevE.84.066122},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato - 2011 - Limits of modularity maximization in community detection(3).pdf:pdf;:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti, Fortunato - 2011 - Limits of modularity maximization in community detection(3).html:html},
journal = {Physical Review E},
month = dec,
number = {6},
pages = {066122},
title = {{Limits of modularity maximization in community detection}},
url = {http://link.aps.org/doi/10.1103/PhysRevE.84.066122 http://pre.aps.org/abstract/PRE/v84/i6/e066122 http://pre.aps.org/pdf/PRE/v84/i6/e066122},
volume = {84},
year = {2011}
}
@article{Petri2014,
abstract = {We present a method to find the best temporal partition at any time-scale and rank the relevance of partitions found at different time-scales. This method is based on random walkers coevolving with the network and as such constitutes a generalization of partition stability to the case of temporal networks. We show that, when applied to a toy model and real datasets, temporal stability uncovers structures that are persistent over meaningful time-scales as well as important isolated events, making it an effective tool to study both abrupt changes and gradual evolution of a network mesoscopic structures.},
archivePrefix = {arXiv},
arxivId = {1404.7170},
author = {Petri, Giovanni and Expert, Paul},
eprint = {1404.7170},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Petri, Expert - 2014 - Temporal stability of network partitions.pdf:pdf},
month = apr,
pages = {15},
title = {{Temporal stability of network partitions}},
url = {http://arxiv.org/abs/1404.7170},
year = {2014}
}
@article{Wehmuth2014,
abstract = {We propose a novel model for representing finite discrete Time-Varying Graphs\~{}(TVGs). We show how key concepts, such as degree, path, and connectivity, are handled in our model. We also analyze the data structures built following our proposed model and demonstrate that, for most practical cases, the asymptotic memory complexity of our model is restricted to the cardinality of the set of edges. Moreover, we prove that if the TVG nodes can be considered as independent entities at each time instant, the analyzed TVG is isomorphic to a directed static graph. This is an important theoretical result since this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a TVG and the behavior of dynamic processes over a TVG. We also show that our unifying model can represent several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other. In contrast to previous models, our proposal is also able to intrinsically model cyclic\~{}(i.e. periodic) behavior in dynamic networks. These representation capabilities attest the expressive power of our proposed unifying model for TVGs.},
archivePrefix = {arXiv},
arxivId = {1402.3488},
author = {Wehmuth, Klaus and Ziviani, Artur and Fleury, Eric},
eprint = {1402.3488},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Wehmuth, Ziviani, Fleury - 2014 - A Unifying Model for Representing Time-Varying Graphs(3).pdf:pdf},
month = feb,
title = {{A Unifying Model for Representing Time-Varying Graphs}},
url = {http://arxiv.org/abs/1402.3488},
year = {2014}
}
@misc{Lin2009,
abstract = {We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. This novel framework will discover communities and capture their evolution with temporal smoothness given by historic community structures. Our approach relies on formulating the problem in terms of maximum a posteriori (MAP) estimation, where the community structure is estimated both by the observed networked data and by the prior distribution given by historic community structures. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.},
author = {Lin, Yu-Ru and Chi, Yun and Zhu, Shenghuo and Sundaram, Hari and Tseng, Belle L.},
booktitle = {ACM Transactions on Knowledge Discovery from Data},
doi = {10.1145/1514888.1514891},
isbn = {9781605580852},
issn = {15564681},
pages = {1--31},
pmid = {17950380},
title = {{Analyzing communities and their evolutions in dynamic social networks}},
volume = {3},
year = {2009}
}
@article{Lancichinetti2010,
abstract = {BACKGROUND: Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks.

METHODOLOGY/PRINCIPAL FINDINGS: We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as "fingerprints" of specific network categories. While community size distributions are always broad, certain categories of networks consist mainly of tree-like communities, while others have denser modules. Average path lengths within communities initially grow logarithmically with community size, but the growth saturates or slows down for communities larger than a characteristic size. This behaviour is related to the presence of hubs within communities, whose roles differ across categories. Also the community embeddedness of nodes, measured in terms of the fraction of links within their communities, has a characteristic distribution for each category.

CONCLUSIONS/SIGNIFICANCE: Our findings, verified by the use of two fundamentally different community detection methods, allow for a classification of real networks and pave the way to a realistic modelling of networks' evolution.},
author = {Lancichinetti, Andrea and Kivel\"{a}, Mikko and Saram\"{a}ki, Jari and Fortunato, Santo},
doi = {10.1371/journal.pone.0011976},
editor = {Sporns, Olaf},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lancichinetti et al. - 2010 - Characterizing the community structure of complex networks(4).pdf:pdf},
issn = {1932-6203},
journal = {PloS one},
keywords = {Animals,Computer Communication Networks,Drosophila melanogaster,Humans,Informatics,Informatics: methods,Information Services,Saccharomyces cerevisiae,Social Support},
month = jan,
number = {8},
pages = {e11976},
pmid = {20711338},
publisher = {Public Library of Science},
title = {{Characterizing the community structure of complex networks.}},
url = {http://dx.plos.org/10.1371/journal.pone.0011976},
volume = {5},
year = {2010}
}
@article{Li2013,
abstract = {Identification of communities in complex networks is an important topic and issue in many fields such as sociology, biology, and computer science. Communities are often defined as groups of related nodes or links that correspond to functional subunits in the corresponding complex systems. While most conventional approaches have focused on discovering communities of nodes, some recent studies start partitioning links to find overlapping communities straightforwardly. In this paper, we propose a new quantity function for link community identification in complex networks. Based on this quantity function we formulate the link community partition problem into an integer programming model which allows us to partition a complex network into overlapping communities. We further propose a genetic algorithm for link community detection which can partition a network into overlapping communities without knowing the number of communities. We test our model and algorithm on both artificial networks and real-world networks. The results demonstrate that the model and algorithm are efficient in detecting overlapping community structure in complex networks.},
annote = {Tr\`{e}s lourd, beaucoup de param\'{e}tres.},
author = {Li, Zhenping and Zhang, Xiang-Sun and Wang, Rui-Sheng and Liu, Hongwei and Zhang, Shihua},
doi = {10.1371/journal.pone.0083739},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Li et al. - 2013 - Discovering link communities in complex networks by an integer programming model and a genetic algorithm.pdf:pdf},
issn = {1932-6203},
journal = {PloS one},
pages = {e83739},
pmid = {24386268},
title = {{Discovering link communities in complex networks by an integer programming model and a genetic algorithm.}},
url = {http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=3875478\&tool=pmcentrez\&rendertype=abstract},
volume = {8},
year = {2013}
}
@article{Lovasz1993,
abstract = {This paper we'll formulate the results in terms of random walks, and mostly restrict our attention to the undirected case. 2 L. Lov'asz},
author = {Lov\'{a}sz, L},
doi = {10.1.1.39.2847},
isbn = {9789638022738},
issn = {03044149},
journal = {Combinatorics Paul Erdos is Eighty},
pages = {1--46},
title = {{Random walks on graphs: A survey}},
url = {http://www.cs.yale.edu/publications/techreports/tr1029.pdf},
volume = {2},
year = {1993}
}
@inproceedings{Baumes2005,
abstract = {In this paper, we present an e\#cient algorithm for finding  overlapping communities in social networks. Our algorithm does not rely  on the contents of the messages and uses the communication graph only.},
author = {Baumes, Jeffrey and Goldberg, Mark and Magdon-ismail, Malik},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Baumes, Goldberg, Magdon-ismail - 2005 - Efficient Identification of Overlapping Communities(3).pdf:pdf},
keywords = {comp,node partition,overlapping},
mendeley-tags = {comp,node partition,overlapping},
pages = {27--36},
title = {{Efficient Identification of Overlapping Communities}},
url = {http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6FCF51BF0D0141DA99AE9B53460EA52F?doi=10.1.1.61.1135\&rep=rep1\&type=pdf},
year = {2005}
}
@inproceedings{Lattanzi2009,
abstract = {In the last decade, structural properties of several natu- rally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world net- works: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to con- ventional wisdom, and are certainly inconsistent with graph models prior to their work. In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known pro- perties of the social networks, as well as densification and shrinking diameter. Our model is based on ideas studied empirically in the social sciences, primarily on the ground- breaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies. We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing short- est paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model. Finally, our work also presents a modular approach to con- necting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).},
address = {New York, New York, USA},
author = {Lattanzi, Silvio and Sivakumar, D.},
booktitle = {Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09},
doi = {10.1145/1536414.1536474},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Lattanzi, Sivakumar - 2009 - Affiliation networks(4).pdf:pdf},
isbn = {9781605585062},
keywords = {densification,diameter,social networks,sparsification.},
month = may,
pages = {427},
publisher = {ACM Press},
title = {{Affiliation networks}},
url = {http://portal.acm.org/citation.cfm?doid=1536414.1536474 http://dl.acm.org/citation.cfm?id=1536414.1536474},
year = {2009}
}
@article{Yoshida2013,
abstract = {We propose weighted line graphs for overlapping community discovery where a node in a network can be assigned to more than one community. For undirected connected networks without self-loops, we propose weighted line graphs by: (1) defining weights of a line graph based on the weights in the original network, and (2) removing self-loops in weighted line graphs, while sustaining their properties. By applying some off-the-shelf node partitioning method to the transformed graph, community labels of adjacent links are assigned to each node in the original network. Experiments are conducted over both synthetic and real-world networks, and the results indicate that the proposed approach can improve the quality of discovered overlapping communities.},
author = {Yoshida, Tetsuya},
doi = {10.1007/s13278-013-0104-1},
issn = {1869-5450, 1869-5469},
journal = {Social Network Analysis and Mining},
keywords = {Data Mining and Knowledge Discovery,Game Theory- Economics- Social and Behav. Sciences,Line graph,Methodology of the Social Sciences,Overlapping community,Statistics for Social Science- Behavorial Science-,Weighted network,complex networks,overlapping},
language = {en},
mendeley-tags = {Data Mining and Knowledge Discovery,Game Theory- Economics- Social and Behav. Sciences,Line graph,Methodology of the Social Sciences,Overlapping community,Statistics for Social Science- Behavorial Science-,Weighted network,complex networks,overlapping},
month = dec,
number = {4},
pages = {1001--1013},
title = {{Weighted line graphs for overlapping community discovery}},
url = {http://link.springer.com/article/10.1007/s13278-013-0104-1},
volume = {3},
year = {2013}
}
@article{Yang2014,
author = {Yang, Jaewon and Leskovec, Jure},
doi = {10.1145/2594454},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Yang, Leskovec - 2014 - Structure and Overlaps of Ground-Truth Communities in Networks(4).pdf:pdf},
issn = {21576904},
journal = {ACM Transactions on Intelligent Systems and Technology},
keywords = {Network communities,affiliation networks,social networks},
month = apr,
number = {2},
pages = {1--35},
publisher = {ACM},
title = {{Structure and Overlaps of Ground-Truth Communities in Networks}},
url = {http://dl.acm.org/citation.cfm?id=2611448.2594454},
volume = {5},
year = {2014}
}
@article{Cheng,
author = {Cheng, James and Wu, Huanhuan and Huang, Yuzhen and Li, Jinfeng},
file = {:home/gaumont/Documents/www2015\_submission\_298.pdf:pdf},
title = {{Reachability and Time-Based Path Queries in Temporal Graphs}}
}
@article{Heymann2012,
abstract = {Finding outliers in datasets is a classical problem of high interest for (dynamic) social network analysis. However, most methods rely on assumptions which are rarely met in practice, such as prior knowledge of some outliers or about normal behavior. We propose here Out skewer, a new approach based on the notion of skewness (a measure of the symmetry of a distribution) and its evolution when extremal values are removed one by one. Our method is easy to set up, it requires no prior knowledge on the system, and it may be used on-line. We illustrate its performance on two data sets representative of many use-cases: evolution of ego-centered views of the internet topology, and logs of queries entered into a search engine.},
author = {Heymann, S. and Latapy, M. and Magnien, C.},
doi = {10.1109/ASONAM.2012.91},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Heymann, Latapy, Magnien - 2012 - Outskewer Using skewness to spot outliers in samples and time series.pdf:pdf},
journal = {Proceedings of the 2012 \ldots},
keywords = {Complex networks,Data models,Distributed databases,Folder - Event detection/Dynamic graphs,Gaussian distribution,Internet,Internet topology,Market research,Social network services,Time series analysis,Topology,anomaly detection,normal behavior,outlier,outlier detection,outskewer,peer-to-peer,query processing,reliability,search engine,search engines,skewness,social network analysis,social networking (online),time series},
mendeley-tags = {Complex networks,Data models,Distributed databases,Folder - Event detection/Dynamic graphs,Gaussian distribution,Internet,Internet topology,Market research,Social network services,Time series analysis,Topology,anomaly detection,normal behavior,outlier,outlier detection,outskewer,peer-to-peer,query processing,reliability,search engine,search engines,skewness,social network analysis,social networking (online),time series},
pages = {527--534},
shorttitle = {Outskewer},
title = {{Outskewer: Using skewness to spot outliers in samples and time series}},
url = {http://ieeexplore.ieee.org/xpl/login.jsp?tp=\&arnumber=6425713\&url=http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=6425713 http://dl.acm.org/citation.cfm?id=2457106},
year = {2012}
}
@article{Granell2015,
abstract = {Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterwards the communities across layers. Alternatively, one can develop dedicated dynamic procedures, so that multiple snapshots are simultaneously taken into account while detecting communities, which allows to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario. Additionally, we perform several tests on various algorithms which show, unsurprisingly, that dynamic techniques are more suitable than static ones to describe community evolution.},
archivePrefix = {arXiv},
arxivId = {1501.05808},
author = {Granell, Clara and Darst, Richard K. and Arenas, Alex and Fortunato, Santo and G\'{o}mez, Sergio},
eprint = {1501.05808},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Granell et al. - 2015 - A benchmark model to assess community structure in evolving networks.pdf:pdf},
month = jan,
pages = {11},
title = {{A benchmark model to assess community structure in evolving networks}},
url = {http://arxiv.org/abs/1501.05808},
year = {2015}
}
@article{Han2014,
abstract = {Temporal graphs capture changes in graphs over time and are becoming a subject that attracts increasing interest from the research communities, for example, to understand temporal characteristics of social interactions on a time-evolving social graph. Chronos is a storage and execution engine designed and optimized specifically for running in-memory iterative graph computation on temporal graphs. Locality is at the center of the Chronos design, where the in-memory layout of temporal graphs and the scheduling of the iterative computation on temporal graphs are carefully designed, so that common "bulk" operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of Chronos further explores the interesting interplay among locality, parallelism, and incremental computation in supporting common mining tasks on temporal graphs. The result is a high-performance temporal-graph system that offers up to an order of magnitude speedup for temporal iterative graph mining compared to a straightforward application of existing graph engines on a series of snapshots.},
author = {Han, W and Miao, Y and Li, K and Wu, Ming and Yang, Fan},
doi = {10.1145/2592798.2592799},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Han et al. - 2014 - Chronos A Graph Engine for Temporal Graph Analysis.pdf:pdf},
isbn = {9781450327046},
journal = {EuroSys '14 Proceedings of the Ninth European Conference on Computer Systems Article No. 1},
title = {{Chronos: A Graph Engine for Temporal Graph Analysis}},
url = {http://dl.acm.org/citation.cfm?id=2592799},
year = {2014}
}
@article{Sarzynska2014,
abstract = {In the study of networks, it is often insightful to use algorithms to determine mesoscale features such as "community structure", in which densely connected sets of nodes constitute "communities" that have sparse connections to other communities. The most popular way of detecting communities algorithmically is to optimize the quality function known as modularity. When optimizing modularity, one compares the actual connections in a (static or time-dependent) network to the connections obtained from a random-graph ensemble that acts as a null model. The communities are then the sets of nodes that are connected to each other densely relative to what is expected from the null model. Clearly, the process of community detection depends fundamentally on the choice of null model, so it is important to develop and analyze novel null models that take into account appropriate features of the system under study. In this paper, we investigate the effects of using null models that take incorporate spatial information, and we propose a novel null model based on the radiation model of population spread. We also develop novel synthetic spatial benchmark networks in which the connections between entities are based on distance or flux between nodes, and we compare the performance of both static and time-dependent radiation null models to the standard ("Newman-Girvan") null model for modularity optimization and a recently-proposed gravity null model. In our comparisons, we use both the above synthetic benchmarks and time-dependent correlation networks that we construct using countrywide dengue fever incidence data for Peru. We also evaluate a recently-proposed correlation null model, which was developed specifically for correlation networks that are constructed from time series, on the epidemic-correlation data.},
archivePrefix = {arXiv},
arxivId = {1407.6297},
author = {Sarzynska, Marta and Leicht, Elizabeth A. and Chowell, Gerardo and Porter, Mason A.},
eprint = {1407.6297},
file = {:home/gaumont/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Sarzynska et al. - 2014 - Null Models for Community Detection in Spatially-Embedded, Temporal Networks(3).pdf:pdf},
month = jul,
title = {{Null Models for Community Detection in Spatially-Embedded, Temporal Networks}},
url = {http://arxiv.org/abs/1407.6297},
year = {2014}
}