Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Fault Tolerant Data Stream Processing in Cooperation with OLTP Engine Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A Parallel Approach to Detect Communities in Evolving Networks

verfasst von : Keshab Nath, Swarup Roy

Erschienen in: Big Data Analytics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

To understand the dynamics, functional and topological aspect of the real-world networks it is necessary to segregate the network into sub-networks, where each member of a sub-network possess analogous characteristics. Numerous number of community finding approaches are proposed in the last few decades to overcome the issues associated with community detection. Although, most of the conventional approaches rely on the premises that networks are static in nature and there won’t be any alternation over time. Moreover, all these approaches are single machine approach and hence exhibits poor scalability.
In this work, we propose a new incremental parallel community detection method, PcDEN (Parallel Community Detection approach in Evolving Networks). Our proposed method can detect communities in dynamic distributed networks. We define a new Affinity score based on intra-community strength between nodes and their neighbors. We also derive a new model to perform community merging, based on common high degree nodes present in both the communities. We tested our algorithm on various real-world networks for our experimentation. Results show that, PcDEN produce satisfactory output with respect to various assessment indices.

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 CbI: Improving Credibility of User-Generated Content on Facebook
Nächstes Kapitel Modeling Sparse and Evolving Data
Fußnoten
Literatur
1.
Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)CrossRef
2.
Haley, B.M., Dong, A., Tumer, I.Y.: Creating faultable network models of complex engineered systems. In: ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers (2014) V02AT03A051-V02AT03A051
3.
Jonsson, P.F., Cavanna, T., Zicha, D., Bates, P.A.: Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis. BMC Bioinform. 7(1), 2 (2006)CrossRef
4.
Gargi, U., Lu, W., Mirrokni, V.S., Yoon, S.: Large-scale community detection on youtube for topic discovery and exploration. In: ICWSM (2011)
5.
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)CrossRef
6.
Kumpula, J.M., Kivelä, M., Kaski, K., Saramäki, J.: Sequential algorithm for fast clique percolation. Phys. Rev. E 78(2), 026109 (2008)CrossRef
7.
Zhang, S., Wang, R.S., Zhang, X.S.: Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Phys. A Stat. Mech. Appl. 374(1), 483–490 (2007)CrossRef
8.
Ren, W., Yan, G., Liao, X., Xiao, L.: Simple probabilistic algorithm for detecting community structure. Phys. Rev. E 79(3), 036111 (2009)CrossRef
9.
10.
Clementi, A., Di Ianni, M., Gambosi, G., Natale, E., Silvestri, R.: Distributed community detection in dynamic graphs. Theor. Comput. Sci. 584, 19–41 (2015)MathSciNetCrossRef
11.
Galluzzi, V.: Real time distributed community structure detection in dynamic networks. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 1236–1241. IEEE (2012)
12.
Prat-Pérez, A., Dominguez-Sal, D., Larriba-Pey, J.L.: High quality, scalable and parallel community detection for large real graphs. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 225–236. ACM (2014)
13.
Papadakis, H., Panagiotakis, C., Fragopoulou, P.: Distributed detection of communities in complex networks using synthetic coordinates. J. Stat. Mech. Theory Exp. 2014(3), P03013 (2014)CrossRef
14.
15.
16.
Clauset, A., Shalizi, C.R., Newman, M.E.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)MathSciNetCrossRef
17.
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)CrossRef
18.
Moon, S., Lee, J.G., Kang, M., Choy, M., Lee, J.W.: Parallel community detection on large graphs with MapReduce and GraphChi. Data Knowl. Eng. 104, 17–31 (2016)CrossRef
19.
20.
Staudt, C.L., Meyerhenke, H.: Engineering parallel algorithms for community detection in massive networks. IEEE Trans. Parallel Distrib. Syst. 27(1), 171–184 (2016)CrossRef
21.
Zhang, Y., Wang, J., Wang, Y., Zhou, L.: Parallel community detection on large networks with propinquity dynamics. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 997–1006. ACM (2009)
22.
Prat-Pérez, A., Dominguez-Sal, D., Brunat, J.M., Larriba-Pey, J.L.: Shaping communities out of triangles. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 1677–1681. ACM (2012)
23.
Leung, I.X., Hui, P., Lio, P., Crowcroft, J.: Towards real-time community detection in large networks. Phys. Rev. E 79(6), 066107 (2009)CrossRef
24.
Jin, S., Yu, P.S., Li, S., Yang, S.: A parallel community structure mining method in big social networks. Math. Probl. Eng. 2015, 13 pages (2015)
25.
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. 105(4), 1118–1123 (2008)CrossRef
26.
Saltz, M., Prat-Pérez, A., Dominguez-Sal, D.: Distributed community detection with the WCC metric. In: Proceedings of the 24th International Conference on World Wide Web, pp. 1095–1100. ACM (2015)
27.
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008(10), P10008 (2008)CrossRef
28.
Palsetia, D., Hendrix, W., Lee, S., Agrawal, A., Liao, W., Choudhary, A.: Parallel community detection algorithm using a data partitioning strategy with pairwise subdomain duplication. In: Kunkel, J.M., Balaji, P., Dongarra, J. (eds.) ISC High Performance 2016. LNCS, vol. 9697, pp. 98–115. Springer, Cham (2016). https://​doi.​org/​10.​1007/​978-3-319-41321-1_​6CrossRef
29.
Zardi, H., Romdhane, L.B., et al.: An o (n2) algorithm for detecting communities of unbalanced sizes in large scale social networks. Knowl. Based Syst. 37, 19–36 (2013)CrossRef
30.
Xie, J., Chen, M., Szymanski, B.K.: LabelRankT: incremental community detection in dynamic networks via label propagation. In: Proceedings of the Workshop on Dynamic Networks Management and Mining, DyNetMM 2013, pp. 25–32. ACM, New York (2013)
31.
Xie, J., Szymanski, B.K.: LabelRank: a stabilized label propagation algorithm for community detection in networks. In: 2013 IEEE 2nd Network Science Workshop (NSW), pp. 138–143. IEEE (2013)
32.
Cazabet, R., Amblard, F., Hanachi, C.: Detection of overlapping communities in dynamical social networks. In: 2010 IEEE Second International Conference on Social Computing (SocialCom), pp. 309–314. IEEE (2010)
33.
Dongen, S.: A cluster algorithm for graphs. Technical report, Amsterdam, The Netherlands (2000)
34.
Aston, N., Hertzler, J., Hu, W., et al.: Overlapping community detection in dynamic networks. J. Softw. Eng. Appl. 7(10), 872 (2014)CrossRef
35.
Xie, J., Szymanski, B.K., Liu, X.: SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW), pp. 344–349. IEEE (2011)
36.
Sun, H., et al.: A parallel self-organizing community detection algorithm based on swarm intelligence for large scale complex networks. In: 2017 IEEE 41st Annual Computer Software and Applications Conference (COMPSAC), vol. 1, pp. 806–815. IEEE (2017)
37.
Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E 80(5), 056117 (2009)CrossRef
38.
39.
Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987)CrossRef
40.
Handl, J., Knowles, J., Kell, D.B.: Computational cluster validation in post-genomic data analysis. Bioinformatics 21(15), 3201–3212 (2005)CrossRef
41.
Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell. 2, 224–227 (1979)CrossRef
42.
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)CrossRef
43.
Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)CrossRef
44.
He, D., Jin, D., Chen, Z., Zhang, W.: Identification of hybrid node and link communities in complex networks. Sci. Rep. 5, 8638 (2015)CrossRef
45.
Cao, X., Wang, X., Jin, D., Cao, Y., He, D.: Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization. Sci. Rep. 3, 2993 (2013)CrossRef
Metadaten
Titel
A Parallel Approach to Detect Communities in Evolving Networks
verfasst von
Keshab Nath
Swarup Roy
Copyright-Jahr
2018
Buch
Big Data Analytics

Print ISBN: 978-3-030-04779-5

Electronic ISBN: 978-3-030-04780-1

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-030-04780-1_13

Premium Partner

    Bildnachweise