nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Clustering Evolving Networks

verfasst von : Tanja Hartmann, Andrea Kappes, Dorothea Wagner

Erschienen in: Algorithm Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Roughly speaking, clustering evolving networks aims at detecting structurally dense subgroups in networks that evolve over time. This implies that the subgroups we seek for also evolve, which results in many additional tasks compared to clustering static networks. We discuss these additional tasks and difficulties resulting thereof and present an overview on current approaches to solve these problems. We focus on clustering approaches in online information from previous time steps in order to incorporate temporal smoothness or to achieve low running time. Moreover, we describe a collection of real world networks and generators for synthetic data that are frequently used for evaluation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Algorithm Engineering in Robust Optimization

Nächstes Kapitel Integrating Sequencing and Scheduling: A Generic Approach with Two Exemplary Industrial Applications

http://www.informatik.uni-trier.de/~ley/db/.

Available at http://www.cs.cmu.edu/~enron/.

For further details and for downloading the whole dataset, please visit http://i11www.iti.uni-karlsruhe.de/en/projects/spp1307/emaildata.

http://realitycommons.media.mit.edu/realitymining.html.

http://www.flickr.com/.

https://dev.twitter.com/docs/streaming-apis#sampling.

http://www.livejournal.com/.

http://www.informatik.uni-trier.de/~ley/db/.

http://arxiv.org/.

http://i11www.iti.uni-karlsruhe.de/en/projects/spp1307/dyneval.

http://www.cs.cornell.edu/projects/kddcup/datasets.html.

http://snap.stanford.edu/data/index.html.

http://www.projecthoneypot.org/.

https://delicious.com/.

http://netsg.cs.sfu.ca/youtubedata/.

http://snap.stanford.edu/data/.

http://www-personal.umich.edu/~mejn/netdata/.

http://deim.urv.cat/~aarenas/data/welcome.htm.

Agarwal, M.K., Ramamritham, K., Bhide, M.: Real time discovery of dense clusters in highly dynamic graphs: identifying real world events in highly dynamic environments. In: Proceedings of the 38th International Conference on Very Large Databases (VLDB 2012), pp. 980–991 (2012)

Aggarwal, C.C., Subbian, K.: Evolutionary network analysis: a survey. ACM Comput. Surv. 47(10), 10:1–10:36 (2014)

Aggarwal, C.C., Xie, Y., Yu, P.S.: Towards community detection in locally heterogeneous networks. In: Proceedings of the Fifth SIAM International Conference on Data Mining, pp. 391–402. SIAM (2011)

Aggarwal, C.C., Zhao, Y., Yu, P.: A framework for clustering massive graph streams. Stat. Anal. Data Min. 3(6), 399–416 (2010). http://dx.doi.org/10.1002/sam.10090 MathSciNetCrossRef

Aldecoa, R., Marín, I.: Deciphering network community structure by surprise. PLoS ONE 6, e24195 (2011)CrossRef

Aldecoa, R., Marín, I.: Closed benchmarks for network community structure characterization. Phys. Rev. E 85, 026109 (2012). http://link.aps.org/doi/10.1103/PhysRevE.85.026109 CrossRef

Aldous, D.J.: Exchangeability and related topics. In: Hennequin, P.L. (ed.) École d’Été de Probabilités de Saint-Flour XIII — 1983. LNM, vol. 1117, pp. 1–198. Springer, Heidelberg (1985). doi:10.1007/BFb0099421. http://dx.doi.org/10.1007/BFb0099421 CrossRef

Anderson, C.J., Wasserman, S., Faust, K.: Building stochastic blockmodels. Soc. Netw. 14, 137–161 (1992)CrossRef

Angel, A., Sarkas, N., Koudas, N., Srivastava, D.: Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Proc. VLDB Endow. 5(6), 574–585 (2012). http://dl.acm.org/citation.cfm?id=2168651.2168658 CrossRef

10.

Arenas, A., Duch, J., Fernandez, A., Gomez, S.: Size reduction of complex networks preserving modularity. New J. Phys. 9(176) (2007). http://dx.doi.org/10.1088/1367-2630/9/6/176

11.

Asur, S., Parthasarathy, S., Ucar, D.: An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Trans. Knowl. Discovery Data 3(4), 16:1–16:36 (2009). http://doi.acm.org/10.1145/1631162.1631164

12.

Aynaud, T., Fleury, E., Guillaume, J.L., Wang, Q.: Communities in evolving networks definitions detection and analysis techniques. In: Mukherjee, A., Choudhury, M., Peruani, F., Ganguly, N., Mitra, B. (eds.) Dynamics on and of Complex Networks. Modeling and Simulation in Science, Engineering and Technology, vol. 2, pp. 159–200. Springer, New York (2013). http://dx.doi.org/10.1007/978-1-4614-6729-8_9

13.

Aynaud, T., Guillaume, J.L.: Static community detection algorithms for evolving networks. In: Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2010), pp. 513–519. IEEE Computer Society (2010)

14.

Backstrom, L., Huttenlocher, D., Kleinberg, J.M., Lan, X.: Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 44–54. ACM Press (2006). http://doi.acm.org/10.1145/1150402.1150412

15.

Bagrow, J.: Evaluating local community methods in networks. J. Stat. Mech.: Theory Exp., P05001 (2008). http://www.iop.org/EJ/abstract/1742-5468/2008/05/P05001/, doi:10.1088/1742-5468/2008/05/P05001

16.

Bansal, S., Bhowmick, S., Paymal, P.: Fast community detection for dynamic complex networks. In: F. Costa, L., Evsukoff, A., Mangioni, G., Menezes, R. (eds.) CompleNet 2010. CCIS, vol. 116, pp. 196–207. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25501-4_20. http://dx.doi.org/10.1007/978-3-642-25501-4_20 CrossRef

17.

Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)MathSciNetCrossRefMATH

18.

Berger-Wolf, T., Kempe, D., Tantipathananandth, C.: A framework for community identification in dynamic social networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press (2007). http://compbio.cs.uic.edu/~tanya/research/pubs/TantipathananandhEtal_NetworkCommunities07.pdf

19.

Berger-Wolf, T., Saia, J.: A framework for analysis of dynamic social networks. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 523–528. ACM Press (2006)

20.

Bichot, C.E., Siarry, P. (eds.): Graph Partitioning. Wiley, Hoboken (2011). http://onlinelibrary.wiley.com/book/10.1002/9781118601181 MATH

21.

Bilgin, C.C., Yener, B.: Dynamic network evolution: models, clustering, anomaly detection. Technical report, Rensselaer University, NY (2008). http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.161.6375

22.

Blondel, V., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008(10) (2008). http://dx.doi.org/10.1088/1742-5468/2008/10/P10008

23.

Bogdanov, P., Mongiovi, M., Singh, A.K.: Mining heavy subgraphs in time-evolving networks. In: Proceedings of the 2011 IEEE International Conference on Data Mining, pp. 81–90. IEEE Computer Society (2011)

24.

Borgwardt, K.M., Kriegel, H.P., Wackersreuther, P.: Pattern mining in frequent dynamic subgraphs. In: Proceedings of the 2006 IEEE International Conference on Data Mining, pp. 818–822. IEEE Computer Society (2006)

25.

Brandes, U., Delling, D., Gaertler, M., Görke, R., Höfer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Trans. Knowl. Data Eng. 20(2), 172–188 (2008). http://doi.ieeecomputersociety.org/10.1109/TKDE.2007.190689 CrossRef

26.

Brandes, U., Gaertler, M., Wagner, D.: Experiments on graph clustering algorithms. In: Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 568–579. Springer, Heidelberg (2003). doi:10.1007/978-3-540-39658-1_52, http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2832&spage=568

27.

Brandes, U., Gaertler, M., Wagner, D.: Engineering graph clustering: models and experimental evaluation. ACM J. Exp. Algorithmics 12(1.1), 1–26 (2007). http://portal.acm.org/citation.cfm?id=1227161.1227162 MathSciNetMATH

28.

Bron, C., Kerbosch, J.A.G.M.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRefMATH

29.

Catalyurek, U., Boman, E., Devine, K., Bozdag, D., Heaphy, R., Riesen, L.A.: Hypergraph-based dynamic load balancing for adaptive scientific computations. In: 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), pp. 1–11. IEEE Computer Society (2007)

30.

Cazabet, R., Amblard, F., Hanachi, C.: Detection of overlapping communities in dynamical social networks. In: Proceedings of the 2010 IEEE Second International Conference on Social Computing, pp. 309–314. IEEE (2010)

31.

Chakrabarti, D.: AutoPart: parameter-free graph partitioning and outlier detection. In: Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, pp. 112–124. ACM Press (2004)

32.

Chakrabarti, D., Kumar, R., Tomkins, A.S.: Evolutionary clustering. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 554–560. ACM Press (2006). http://doi.acm.org/10.1145/1150402.1150467

33.

Chen, J., Fagnan, J., Goebel, R., Rabbany, R., Sangi, F., Takaffoli, M., Verbeek, E., Zaïane, O.R.: Meerkat: community mining with dynamic social networks. In: Proceedings in the 10th IEEE International Conference on Data Mining - Workshops, pp. 1377–1380. IEEE Computer Society, December 2010

34.

Chen, J., Zaïane, O.R., Goebel, R.: Detecting communities in large networks by iterative local expansion. In: Proceedings of the 2009 IEEE International Conference on Computational Aspects of Social Networks, pp. 105–112. IEEE Computer Society (2009)

35.

Chi, Y., Song, X., Zhou, D., Hino, K., Tseng, B.L.: Evolutionary spectral clustering by incorporating temporal smoothness. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 153–162. ACM Press (2007). http://doi.acm.org/10.1145/1281192.1281212

36.

Clauset, A.: Finding local community structure in networks. Phys. Rev. E 72(2), 026132 (2005). http://link.aps.org/doi/10.1103/PhysRevE.72.026132 CrossRef

37.

Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(066111) (2004). http://link.aps.org/abstract/PRE/v70/e066111

38.

Condon, A., Karp, R.M.: Algorithms for graph partitioning on the planted partition model. Randoms Struct. Algorithms 18(2), 116–140 (2001). http://dx.doi.org/10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2

39.

Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7(2), 279–301 (1989). http://dx.doi.org/10.1016/0743-7315(89)90021-X CrossRef

40.

Davis, A., Gardner, B., Gardner, M.R.: Deep South. University of Chicago Press, Chicago (1941)

41.

Delling, D., Gaertler, M., Görke, R., Wagner, D.: Engineering comparators for graph clusterings. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 131–142. Springer, Heidelberg (2008). doi:10.1007/978-3-540-68880-8_14 CrossRef

42.

Derényi, I., Palla, G., Vicsek, T.: Clique percolation in random networks. Phys. Rev. Lett. 94, 160202 (2005). http://link.aps.org/abstract/PRL/v94/e160202 CrossRef

43.

Ding, C.H.Q., He, X., Zha, H., Gu, M., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings of the 2001 IEEE International Conference on Data Mining, pp. 107–114. IEEE Computer Society (2001). http://dx.doi.org/10.1109/ICDM.2001.989507

44.

Dinh, T.N., Nguyen, N.P., Thai, M.T.: An adaptive approximation algorithm for community detection in dynamic scale-free networks. In: Proceedings of the 32th Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom). IEEE Computer Society Press (2013, to appear)

45.

Dinh, T.N., Shin, I., Thai, N.K., Thai, M.T., Znati, T.: A general approach for modules identification in evolving networks. In: Hirsch, M.J., Pardalos, P.M., Murphey, R. (eds.) Dynamics of Information Systems. Springer Optimization and Its Applications, vol. 40, pp. 83–100. Springer, New York (2010). http://dx.doi.org/10.1007/978-1-4419-5689-7_4 CrossRef

46.

Dinh, T.N., Thai, M.T.: Community detection in scale-free networks: approximation algorithms for maximizing modularity. IEEE J. Sel. Areas Commun. 31(6), 997–1006 (2013)CrossRef

47.

Dinh, T.N., Ying, X., Thai, M.T.: Towards social-aware routing in dynamic communication networks. In: Proceedings of the 28th International Performance Computing and Communications Conference (IPCCC), pp. 161–168 (2009)

48.

Doll, C., Hartmann, T., Wagner, D.: Fully-dynamic hierarchical graph clustering using cut trees. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 338–349. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22300-6_29 CrossRef

49.

Duan, D., Li, Y., Li, R., Lu, Z.: Incremental k-clique clustering in dynamic social networks. Artif. Intell. 38(2), 129–147 (2012)CrossRef

50.

Eagle, N., Pentland, A.: Reality mining: sensing complex social systems. J. Pers. Ubiquit. Comput. 10(4), 255–268 (2006)CrossRef

51.

Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 226–231. ACM Press (1996)

52.

Everett, M.G., Borgatti, S.P.: Analyzing clique overlap. Connections 21(1), 49–61 (1998)

53.

Falkowski, T.: Community analysis in dynamic social networks. Ph.D. thesis, Otto-von-Guericke-Universität Magdeburg (2009)

54.

Falkowski, T., Bartelheimer, J., Spiliopoulou, M.: Mining and visualizing the evolution of subgroups in social networks. In: IEEE/WIC/ACM International Conference on Web Intelligence, pp. 52–58. IEEE (2006)

55.

Falkowski, T., Barth, A., Spiliopoulou, M.: Dengraph: A density-based community detection algorithm. In: IEEE/WIC/ACM International Conference on Web Intelligence, pp. 112–115. IEEE (2007)

56.

Fan, Y., Li, M., Zhang, P., Wu, J., Di, Z.: Accuracy and precision of methods for community identification in weighted networks. Phys. A 377(1), 363–372 (2007). http://www.sciencedirect.com/science/article/pii/S0378437106012386 CrossRef

57.

Flake, G.W., Tarjan, R.E., Tsioutsiouliklis, K.: Graph clustering and minimum cut trees. Internet Math. 1(4), 385–408 (2004). http://www.internetmathematics.org/volumes/1.htm MathSciNetCrossRefMATH

58.

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010). http://www.sciencedirect.com/science/journal/03701573 MathSciNetCrossRef

59.

Fortunato, S., Barthélemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. U.S.A. 104(1), 36–41 (2007). http://www.pnas.org/content/104/1/36.full.pdf CrossRef

60.

Gaertler, M., Görke, R., Wagner, D.: Significance-driven graph clustering. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 11–26. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72870-2_2, http://www.springerlink.com/content/nrq6tlm286808887/?p=65f77ccbb2674a16b9a67da6bb370dc7&pi=5

61.

Gehweiler, J., Meyerhenke, H.: A distributed diffusive heuristic for clustering a virtual P2P supercomputer. In: Proceedings of the 7th High-Performance Grid Computing Workshop (HGCW 2010) in Conjunction with 24th International Parallel and Distributed Processing Symposium (IPDPS 2010), pp. 1–8. IEEE Computer Society (2010)

62.

Gilbert, H.: Random graphs. Ann. Math. Stat. 30(4), 1141–1144 (1959)CrossRefMATH

63.

Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. U.S.A. 99(12), 7821–7826 (2002)MathSciNetCrossRefMATH

64.

Gloor, P.A., Zhao, Y.: TeCFlow - a temporal communication flow visualizer for social network analysis. In: ACM CSCW Workshop on Social Networks (2004)

65.

Gomory, R.E., Hu, T.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551–570 (1961)MathSciNetCrossRefMATH

66.

Görke, R.: An algorithmic walk from static to dynamic graph clustering. Ph.D. thesis, Fakultät für Informatik, February 2010. http://digbib.ubka.uni-karlsruhe.de/volltexte/1000018288

67.

Görke, R., Hartmann, T., Wagner, D.: Dynamic graph clustering using minimum-cut trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 339–350. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03367-4_30. http://dx.doi.org/10.1007/978-3-642-03367-4_30 CrossRef

68.

Görke, R., Hartmann, T., Wagner, D.: Dynamic graph clustering using minimum-cut trees. J. Graph Algorithms Appl. 16(2), 411–446 (2012)MathSciNetCrossRefMATH

69.

Görke, R., Kluge, R., Schumm, A., Staudt, C., Wagner, D.: An efficient generator for clustered dynamic random networks. In: Even, G., Rawitz, D. (eds.) MedAlg 2012. LNCS, vol. 7659, pp. 219–233. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34862-4_16 CrossRef

70.

Görke, R., Maillard, P., Schumm, A., Staudt, C., Wagner, D.: Dynamic graph clustering combining modularity and smoothness. ACM J. Exp. Algorithmics 18(1), 1.5:1.1–1.5:1.29 (2013). http://dl.acm.org/citation.cfm?doid=2444016.2444021 MathSciNetMATH

71.

Görke, R., Schumm, A., Wagner, D.: Density-constrained graph clustering. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 679–690. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22300-6_58. http://link.springer.com/chapter/10.1007/978-3-642-22300-6_58?null CrossRef

72.

Görke, R., Staudt, C.: A generator for dynamic clustered random graphs. Technical report, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH) (2009). http://i11www.iti.uni-karlsruhe.de/projects/spp1307/dyngen, informatik, Uni Karlsruhe, TR 2009-7

73.

Grady, L., Schwartz, E.I.: Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28(3), 469–475 (2006)CrossRef

74.

Greene, D., Doyle, D., Cunningham, P.: Tracking the evolution of communities in dynamic social networks. In: Proceedings of the 2010 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 176–183. IEEE Computer Society (2010)

75.

Guimerà, R., Sales-Pardo, M., Amaral, L.A.N.: Module identification in bipartite and directed networks. Phys. Rev. E 76, 036102 (2007). http://link.aps.org/doi/10.1103/PhysRevE.76.036102 CrossRef

76.

Held, P., Kruse, R.: Analysis and visualization of dynamic clusterings. In: Proceedings of the 46th Hawaii International Conference on System Sciences, pp. 1385–1393 (2013)

77.

Hopcroft, J.E., Khan, O., Kulis, B., Selman, B.: Tracking evolving communities in large linked networks. Proc. Natl. Acad. Sci. U.S.A. 101, 5244–5253 (2004). http://www.pnas.org/content/101/suppl.1/5249.abstract CrossRef

78.

Jaccard, P.: The distribution of flora in the alpine zone. New Phytol. 11(2), 37–50 (1912)CrossRef

79.

Kannan, R., Vempala, S., Vetta, A.: On clusterings: good, bad, spectral. J. ACM 51(3), 497–515 (2004)MathSciNetCrossRefMATH

80.

Kim, K., McKay, R.I., Moon, B.R.: Multiobjective evolutionary algorithms for dynamic social network clustering. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 1179–1186. ACM Press (2010)

81.

Kim, M.S., Han, J.: A particle-and-density based evolutionary clustering method for dynamic networks. In: Proceedings of the 35th International Conference on Very Large Databases (VLDB 2009), pp. 622–633 (2009)

82.

Kullback, S., Leibler, R.A.: On information and sufficiency. Ann. Math. Stat. 22(1), 79–86 (1951)MathSciNetCrossRefMATH

83.

Kumar, R., Novak, J., Tomkins, A.S.: Structure and evolution of online social networks. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 611–617. ACM Press (2006). http://doi.acm.org/10.1145/1150402.1150476

84.

Lai, J.H., Wang, C.D., Yu, P.: Dynamic community detection in weighted graph streams. In: Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 151–161. SIAM (2013)

85.

Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80(1), 016118 (2009)CrossRef

86.

Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure of complex networks. New J. Phys. 11(033015) (2009). http://www.iop.org/EJ/njp

87.

Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)CrossRef

88.

Lee, C., Cunningham, P.: Benchmarking community detection methods on social media data. Preprint, arXiv:1302.0739 [cs.SI] (2013)

89.

Leicht, E.A., Newman, M.E.J.: Community structure in directed networks. Phys. Rev. Lett. 100(11), 118703+ (2008). http://dx.doi.org/10.1103/PhysRevLett.100.118703 CrossRef

90.

Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999). http://portal.acm.org/citation.cfm?doid=331524.331526 MathSciNetCrossRefMATH

91.

Leskovec, J., Backstrom, L., Kumar, R., Tomkins, A.S.: Microscopic evolution of social networks. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 462–470. ACM Press (2008)

92.

Leskovec, J., Kleinberg, J.M., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 177–187. ACM Press (2005). http://portal.acm.org/citation.cfm?id=1081893

93.

Lin, Y.R., Chi, Y., Zhu, S., Sundaram, H., Tseng, B.L.: Analyzing communities and their evolutions in dynamic social networks. ACM Trans. Knowl. Discov. Data 3(2), 8:1–8:31 (2009)CrossRef

94.

Luo, F., Wang, J.Z., Promislow, E.: Exploring local community structures in large networks. In: IEEE/WIC/ACM International Conference on Web Intelligence, pp. 233–239. IEEE (2006). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4061371

95.

von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395–416 (2007). http://www.springerlink.com/content/jq1g17785n783661/ MathSciNetCrossRef

96.

Meyerhenke, H.: Dynamic load balancing for parallel numerical simulations based on repartitioning with disturbed diffusion. In: 15th International Conference on Parallel and Distributed Systems (ICPADS), pp. 150–157. IEEE (2009)

97.

Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions. J. Parallel Distrib. Comput. 69(9), 750–761 (2009). http://dx.doi.org/10.1016/j.jpdc.2009.04.005 CrossRef

98.

Meyerhenke, H., Monien, B., Schamberger, S.: Graph partitioning and disturbed diffusion. Parallel Comput. 35(10–11), 544–569 (2009). http://dx.doi.org/10.1016/j.parco.2009.09.006 CrossRef

99.

Mirkin, B.: Eleven ways to look at the chi-squared coefficient for contingency tables. Am. Stat. 55(2), 111–120 (2001). http://www.jstor.org/stable/2685997 MathSciNetCrossRef

100.

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Vis. Lang. Comput. 6(2), 183–210 (1995). http://www.sciencedirect.com/science/article/pii/S1045926X85710105 CrossRef

101.

Moody, J., McFarland, D., Bender-deMoll, S.: Dynamic network visualization. Am. J. Sociol. 110(4), 1206–1241 (2005)CrossRef

102.

Muelder, C., Ma, K.L.: Rapid graph layout using space filling curves. IEEE Trans. Vis. Comput. Graph. 14(6), 1301–1308 (2008)CrossRef

103.

Muelder, C., Ma, K.L.: A treemap based method for rapid layout of large graphs. In: Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2008), pp. 231–238 (2008)

104.

Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003). http://dx.doi.org/10.1137/S003614450342480 MathSciNetCrossRefMATH

105.

Newman, M.E.J.: Analysis of weighted networks. Phys. Rev. E 70(056131), 1–9 (2004). http://link.aps.org/abstract/PRE/v70/e056131

106.

Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J. B 38(2), 321–330 (2004). http://www.springerlink.com/content/5GTDACX17BQV6CDC CrossRef

107.

Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(026113), 1–16 (2004). http://link.aps.org/abstract/PRE/v69/e026113

108.

Nguyen, N.P., Dinh, T.N., Ying, X., Thai, M.T.: Adaptive algorithms for detecting community structure in dynamic social networks. In: Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom), pp. 2282–2290. IEEE Computer Society Press (2011)

109.

Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech.: Theory Exp. 2009(03), p03024 (23pp) (2009). http://stacks.iop.org/1742-5468/2009/P03024

110.

Ning, H., Xu, W., Chi, Y., Gong, Y., Huang, T.: Incremental spectral clustering with application to monitoring of evolving blog communities. In: Proceedings of the 2007 SIAM International Conference on Data Mining, pp. 261–272. SIAM (2007)

111.

Ning, H., Xu, W., Chi, Y., Gong, Y., Huang, T.: Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recogn. 43, 113–127 (2010)CrossRefMATH

112.

Ovelgönne, M., Geyer-Schulz, A.: An ensemble learning strategy for graph clustering. In: Graph Partitioning and Graph Clustering: Tenth DIMACS Implementation Challenge. DIMACS Book, vol. 588, pp. 187–206. American Mathematical Society (2013). http://www.ams.org/books/conm/588/11701

113.

Palla, G., Barabási, A.L., Vicsek, T.: Quantifying social group evolution. Nature 446, 664–667 (2007). http://www.nature.com/nature/journal/v446/n7136/abs/nature05670.html CrossRef

114.

Pang, S., Chen, C., Wei, T.: A realtime community detection algorithm: incremental label propagation. In: First International Conference on Future Information Networks (ICFIN 2009), pp. 313–317. IEEE (2009)

115.

Park, Y., Song, M.: A genetic algorithm for clustering problems. In: Proceedings of the 3rd Annual Conference on Genetic Programming, pp. 568–575 (1998)

116.

Patro, R., Duggal, G., Sefer, E., Wang, H., Filippova, D., Kingsford, C.: The missing models: a data-driven approach for learning how networks grow. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 42–50. ACM Press (2012)

117.

Pearson, K.: On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling. Philos. Mag. Ser. 5 50(302), 157–175 (1900)CrossRefMATH

118.

Pons, P., Latapy, M.: Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10(2), 191–218 (2006). http://www.cs.brown.edu/publications/jgaa/ MathSciNetCrossRefMATH

119.

Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007). http://link.aps.org/doi/10.1103/PhysRevE.76.036106 CrossRef

120.

Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971). http://www.jstor.org/stable/2284239?origin=crossref CrossRef

121.

Riedy, J., Bader, D.A.: Multithreaded community monitoring for massive streaming graph data. In: Workshop on Multithreaded Architectures and Applications (MTAAP 2013) (2013, to appear)

122.

Riedy, E.J., Meyerhenke, H., Ediger, D., Bader, D.A.: Parallel community detection for massive graphs. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2011. LNCS, vol. 7203, pp. 286–296. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31464-3_29. http://dx.doi.org/10.1007/978-3-642-31464-3_29 CrossRef

123.

Rissanen, J.: Modeling by shortest data description. Automatica 14(5), 465–471 (1978)CrossRefMATH

124.

Rotta, R., Noack, A.: Multilevel local search algorithms for modularity clustering. ACM J. Exp. Algorithmics 16, 2.3:2.1–2.3:2.27 (2011). http://doi.acm.org/10.1145/1963190.1970376 MathSciNetMATH

125.

Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987). http://www.sciencedirect.com/science/article/pii/0377042787901257 CrossRefMATH

126.

Saha, B., Mitra, P.: Dynamic algorithm for graph clustering using minimum cut tree. In: Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, pp. 667–671. IEEE Computer Society, December 2006. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4063709

127.

Saha, B., Mitra, P.: Dynamic algorithm for graph clustering using minimum cut tree. In: Proceedings of the 2007 SIAM International Conference on Data Mining, pp. 581–586. SIAM (2007). http://www.siam.org/proceedings/datamining/2007/dm07.php

128.

Sallaberry, A., Muelder, C., Ma, K.-L.: Clustering, visualizing, and navigating for large dynamic graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 487–498. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36763-2_43. http://dx.doi.org/10.1007/978-3-642-36763-2_43 CrossRef

129.

Sawardecker, E.N., Sales-Pardo, M., Amaral, L.A.N.: Detection of node group membership in networks with group overlap. Eur. Phys. J. B 67, 277–284 (2009). http://dx.doi.org/10.1140/epjb/e2008-00418-0 CrossRefMATH

130.

Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007). http://dx.doi.org/10.1016/j.cosrev.2007.05.001 MathSciNetCrossRefMATH

131.

Schuetz, P., Caflisch, A.: Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Phys. Rev. E 77(046112) (2008). http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PLEEE8000077000004046112000001&idtype=cvips&gifs=yes

132.

Shen, H., Cheng, X., Cai, K., Hu, M.B.: Detect overlapping and hierarchical community structure in networks. Phys. A: Stat. Mech. Appl. 388(8), 1706–1712 (2009). http://www.sciencedirect.com/science/article/pii/S0378437108010376 CrossRef

133.

Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000). http://doi.ieeecs.org/10.1109/34.868688 CrossRef

134.

Sibson, R.: Slink: an optimally efficient algorithm for the single-link cluster method. Comput. J. 16(1), 30–34 (1973). http://dx.doi.org/10.1093/comjnl/16.1.30 MathSciNetCrossRef

135.

Šíma, J., Schaeffer, S.E.: On the NP-completeness of some graph cluster measures. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 530–537. Springer, Heidelberg (2006). doi:10.1007/11611257_51. http://dx.doi.org/10.1007/11611257_51

136.

Snijders, T.A., Nowicki, K.: Estimation and prediction of stochastic blockmodels for graphs with latent block structure. J. Classif. 14, 75–100 (1997)MathSciNetCrossRefMATH

137.

Spiliopoulou, M., Ntoutsi, I., Theodoridis, Y., Schult, R.: MONIC: modeling and monitoring cluster transitions. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 706–711. ACM Press (2006). http://doi.acm.org/10.1145/1150402.1150491

138.

Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230. ACM Press (2012)

139.

Staudt, C., Meyerhenke, H.: Engineering high-performance community detection heuristics for massive graphs. In: Proceedings of the 2013 International Conference on Parallel Processing. Conference Publishing Services (CPS) (2013)

140.

Sun, J., Yu, P.S., Papadimitriou, S., Faloutsos, C.: Graphscope: parameter-free mining of large time-evolving graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 687–696. ACM Press (2007). http://portal.acm.org/citation.cfm?id=1281192.1281266&coll=Portal&dl=GUIDE&CFID=54298929&CFTOKEN=41087406

141.

Sun, Y., Tang, J., Han, J., Gupta, M., Zhao, B.: Community evolution detection in dynamic heterogeneous information networks. In: Proceedings of the Eighth Workshop on Mining and Learning with Graphs, pp. 137–146. ACM Press (2010). http://doi.acm.org/10.1145/1830252.1830270

142.

Sundaresan, S.R., Fischhoff, I.R., Dushoff, J.: Network metrics reveal differences in social organization between two fission-fusion species, Grevy’s zebra and onager. Oecologia 151(1), 140–149 (2007)CrossRef

143.

Takaffoli, M., Fagnan, J., Sangi, F., Zaïane, O.R.: Tracking changes in dynamic information networks. In: Proceedings of the 2011 IEEE International Conference on Computational Aspects of Social Networks, pp. 94–101. IEEE Computer Society (2011)

144.

Takaffoli, M., Rabbany, R., Zaïane, O.R.: Incremental local community identification in dynamic social networks. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE Computer Society (2013, to appear)

145.

Tong, H., Papadimitriou, S., Sun, J., Yu, P.S., Faloutsos, C.: Colibri: fast mining of large static and dynamic graphs. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 686–694. ACM Press (2008). http://doi.acm.org/10.1145/1401890.1401973

146.

Vázquez, A.: Growing network with local rules: preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E 67, 056104 (2003). http://link.aps.org/doi/10.1103/PhysRevE.67.056104 CrossRef

147.

Viswanath, B., Mislove, A., Cha, M., Gummadi, P.K.: On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM Workshop on Online Social Networks, pp. 37–42. ACM Press (2009). http://doi.acm.org/10.1145/1592665.1592675

148.

Wagner, S., Wagner, D.: Comparing clusterings - an overview. Technical report 2006-04, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH) (2007). http://digbib.ubka.uni-karlsruhe.de/volltexte/1000011477

149.

Wang, Y.J., Wong, G.Y.: Stochastic blockmodels for directed graphs. J. Am. Stat. Assoc. 82, 8–19 (1987)MathSciNetCrossRefMATH

150.

Watts, D.J.: Networks, dynamics, and the small-world phenomenon. Am. J. Sociol. 105, 493–527 (1999)CrossRef

151.

Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)CrossRef

152.

Xie, J., Chen, M., Szymanski, B.K.: LabelRankT: incremental community detection in dynamic networks via label propagation. CoRR abs/1305.2006 (2013). http://arxiv.org/abs/1305.2006

153.

Xie, J., Szymanski, B.K.: LabelRank: a stabilized label propagation algorithm for community detection in networks. CoRR abs/1303.0868 (2013). http://arxiv.org/abs/1303.0868

154.

Xu, K.S., Kliger, M., Hero, A.O.: Tracking communities in dynamic social networks. In: Salerno, J., Yang, S.J., Nau, D., Chai, S.-K. (eds.) SBP 2011. LNCS, vol. 6589, pp. 219–226. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19656-0_32 CrossRef

155.

Xu, X., Yuruk, N., Feng, Z., Schweiger, T.A.J.: Scan: a structural clustering algorithm for networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 824–833. ACM Press (2007)

156.

Yang, T., Chi, Y., Zhu, S., Jin, R.: Detecting communities and their evolutions in dynamic social networks - a Bayesian approach. Mach. Learn. 82(2), 157–189 (2011)MathSciNetCrossRefMATH

157.

Yu, K., Yu, S., Tresp, V.: Soft clustering on graphs. In: Advances in Neural Information Processing Systems 18, p. 5. MIT Press (2006)

158.

Yu, S.X., Shi, J.: Multiclass spectral clustering. In: Proceedings of the 9th IEEE International Conference on Computer Vision, pp. 313–319 (2003)

159.

Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452–473 (1977)CrossRef

160.

Zhao, Y., Yu, P.S.: On graph stream clustering with side information. In: Proceedings of the Seventh SIAM International Conference on Data Mining, pp. 139–150. SIAM (2013)

161.

Zheleva, E., Sharara, H., Getoor, L.: Co-evolution of social and affiliation networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1007–1016. ACM Press (2009). http://doi.acm.org/10.1145/1557019.1557128

162.

Zhou, H.: Network landscape from a Brownian particle’s perspective. Phys. Rev. E 67, 041908 (2003). http://link.aps.org/doi/10.1103/PhysRevE.67.041908 CrossRef

Titel: Clustering Evolving Networks
verfasst von: Tanja Hartmann
Andrea Kappes
Dorothea Wagner
Verlag: Springer International Publishing
Buch: Algorithm Engineering
Print ISBN: 978-3-319-49486-9

Electronic ISBN: 978-3-319-49487-6

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-49487-6_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"