Skip to main content
Top

2018 | OriginalPaper | Chapter

A Parallel Approach to Detect Communities in Evolving Networks

Authors : Keshab Nath, Swarup Roy

Published in: Big Data Analytics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Literature
1.
2.
go back to reference 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 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.
go back to reference 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 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.
go back to reference Gargi, U., Lu, W., Mirrokni, V.S., Yoon, S.: Large-scale community detection on youtube for topic discovery and exploration. In: ICWSM (2011) Gargi, U., Lu, W., Mirrokni, V.S., Yoon, S.: Large-scale community detection on youtube for topic discovery and exploration. In: ICWSM (2011)
5.
go back to reference 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 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.
go back to reference Kumpula, J.M., Kivelä, M., Kaski, K., Saramäki, J.: Sequential algorithm for fast clique percolation. Phys. Rev. E 78(2), 026109 (2008)CrossRef 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.
go back to reference 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 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.
go back to reference Ren, W., Yan, G., Liao, X., Xiao, L.: Simple probabilistic algorithm for detecting community structure. Phys. Rev. E 79(3), 036111 (2009)CrossRef Ren, W., Yan, G., Liao, X., Xiao, L.: Simple probabilistic algorithm for detecting community structure. Phys. Rev. E 79(3), 036111 (2009)CrossRef
10.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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 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
15.
16.
go back to reference Clauset, A., Shalizi, C.R., Newman, M.E.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)MathSciNetCrossRef Clauset, A., Shalizi, C.R., Newman, M.E.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)MathSciNetCrossRef
17.
go back to reference Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)CrossRef Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)CrossRef
18.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Dongen, S.: A cluster algorithm for graphs. Technical report, Amsterdam, The Netherlands (2000) Dongen, S.: A cluster algorithm for graphs. Technical report, Amsterdam, The Netherlands (2000)
34.
go back to reference Aston, N., Hertzler, J., Hu, W., et al.: Overlapping community detection in dynamic networks. J. Softw. Eng. Appl. 7(10), 872 (2014)CrossRef Aston, N., Hertzler, J., Hu, W., et al.: Overlapping community detection in dynamic networks. J. Softw. Eng. Appl. 7(10), 872 (2014)CrossRef
35.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E 80(5), 056117 (2009)CrossRef Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E 80(5), 056117 (2009)CrossRef
39.
go back to reference Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987)CrossRef 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.
go back to reference Handl, J., Knowles, J., Kell, D.B.: Computational cluster validation in post-genomic data analysis. Bioinformatics 21(15), 3201–3212 (2005)CrossRef Handl, J., Knowles, J., Kell, D.B.: Computational cluster validation in post-genomic data analysis. Bioinformatics 21(15), 3201–3212 (2005)CrossRef
41.
go back to reference Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell. 2, 224–227 (1979)CrossRef Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell. 2, 224–227 (1979)CrossRef
42.
go back to reference 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 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.
go back to reference 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 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.
go back to reference He, D., Jin, D., Chen, Z., Zhang, W.: Identification of hybrid node and link communities in complex networks. Sci. Rep. 5, 8638 (2015)CrossRef 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.
go back to reference 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 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
Metadata
Title
A Parallel Approach to Detect Communities in Evolving Networks
Authors
Keshab Nath
Swarup Roy
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-030-04780-1_13

Premium Partner