{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:32:10Z","timestamp":1742941930529,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662464847"},{"type":"electronic","value":"9783662464854"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46485-4_6","type":"book-chapter","created":{"date-parts":[[2015,2,21]],"date-time":"2015-02-21T10:51:17Z","timestamp":1424515877000},"page":"153-179","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast Disjoint and Overlapping Community Detection"],"prefix":"10.1007","author":[{"given":"Yi","family":"Song","sequence":"first","affiliation":[]},{"given":"St\u00e9phane","family":"Bressan","sequence":"additional","affiliation":[]},{"given":"Gillian","family":"Dobbie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,22]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1038\/nature09182","volume":"466","author":"Y-Y Ahn","year":"2010","unstructured":"Ahn, Y.-Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466, 761 (2010)","journal-title":"Nature"},{"unstructured":"Baumes, J., Goldberg, M.K., Krishnamoorthy, M.S., Magdon-Ismail, M., Preston, N.: Finding communities by clustering a graph into overlapping subgraphs. In: IADIS AC, pp. 97\u2013104 (2005)","key":"6_CR2"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/11427995_3","volume-title":"Intelligence and Security Informatics","author":"J Baumes","year":"2005","unstructured":"Baumes, J., Goldberg, M., Magdon-Ismail, M.: Efficient identification of overlapping communities. In: Kantor, P., Muresan, G., Roberts, F., Zeng, D.D., Wang, F.-Y., Chen, H., Merkle, R.C. (eds.) ISI 2005. LNCS, vol. 3495, pp. 27\u201336. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Cao, X., Wang, X., Di, J., Cao, Y., Dongxiao, H.: Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization. Scientific report (2013)","key":"6_CR4","DOI":"10.1038\/srep02993"},{"issue":"2","key":"6_CR5","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s10618-010-0186-6","volume":"21","author":"W Chen","year":"2010","unstructured":"Chen, W., Liu, Z., Sun, X., Wang, Y.: A game-theoretic framework to identify overlapping communities in social networks. Data Min. Knowl. Discov. 21(2), 224\u2013240 (2010)","journal-title":"Data Min. Knowl. Discov."},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"026132","DOI":"10.1103\/PhysRevE.72.026132","volume":"72","author":"A Clauset","year":"2005","unstructured":"Clauset, A.: Finding local community structure in networks. Phys. Rev. E 72, 026132 (2005)","journal-title":"Phys. Rev. E"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)","journal-title":"Phys. Rev. E"},{"doi-asserted-by":"crossref","unstructured":"Coscia, M., Rossetti, G., Giannotti, F., Pedreschi, D.: Demon: a local-first discovery method for overlapping communities. CoRR (2012)","key":"6_CR8","DOI":"10.1145\/2339530.2339630"},{"unstructured":"CUDA-Zone. http:\/\/www.nvidia.com\/object\/what_is_cuda_new.html","key":"6_CR9"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"065103","DOI":"10.1103\/PhysRevE.68.065103","volume":"68","author":"L Danon","year":"2003","unstructured":"Danon, L., Diaz-Guilera, A., Giralt, F., Arenas, A.: Self-similar community structure in a network of human interactions. Phys. Rev. E 68, 065103 (2003)","journal-title":"Phys. Rev. E"},{"doi-asserted-by":"crossref","unstructured":"Du, N., Wu, B., Pei, X., Wang, B., Xu, L.: Community detection in large-scale social networks. In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis, WebKDD\/SNA-KDD 2007, pp. 16\u201325. ACM (2007)","key":"6_CR11","DOI":"10.1145\/1348549.1348552"},{"unstructured":"Email-URV. http:\/\/deim.urv.cat\/aarenas\/data\/welcome.htm","key":"6_CR12"},{"doi-asserted-by":"crossref","unstructured":"Fortunato, S., Lancichinetti, A.: Community detection algorithms: a comparative analysis: invited presentation, extended abstract. In: VALUETOOLS 2009. ICST, Brussels, Belgium (2009)","key":"6_CR13","DOI":"10.4108\/ICST.VALUETOOLS2009.8046"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1038\/nature03607","volume":"435","author":"IF Gergely Palla","year":"2005","unstructured":"Gergely Palla, I.F., Derenyi, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814\u2013818 (2005)","journal-title":"Nature"},{"issue":"12","key":"6_CR15","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99(12), 7821\u20137826 (2002)","journal-title":"Proc. Nat. Acad. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gleich, D.F., Seshadhri, C.: Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012. ACM, New York (2012)","key":"6_CR16","DOI":"10.1145\/2339530.2339628"},{"doi-asserted-by":"crossref","unstructured":"Goldberg, M.K., Kelley, S., Magdon-Ismail, M., Mertsalov, K., Wallace, A.: Finding overlapping communities in social networks. In: SocialCom\/PASSAT, pp. 104\u2013113 (2010)","key":"6_CR17","DOI":"10.1109\/SocialCom.2010.24"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-540-74976-9_12","volume-title":"Knowledge Discovery in Databases: PKDD 2007","author":"S Gregory","year":"2007","unstructured":"Gregory, S.: An algorithm to find overlapping community structure in networks. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladeni\u010d, D., Skowron, A. (eds.) PKDD 2007. LNCS (LNAI), vol. 4702, pp. 91\u2013102. Springer, Heidelberg (2007)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-540-87479-9_45","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"S Gregory","year":"2008","unstructured":"Gregory, S.: A fast algorithm to find overlapping communities in networks. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008, Part I. LNCS (LNAI), vol. 5211, pp. 408\u2013423. Springer, Heidelberg (2008)"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/3-540-45294-X_3","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"D Harel","year":"2001","unstructured":"Harel, D., Koren, Y.: On clustering using random walks. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol. 2245, pp. 18\u201341. Springer, Heidelberg (2001)"},{"issue":"2","key":"6_CR21","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1177\/104649647100200201","volume":"2","author":"PW Holland","year":"1971","unstructured":"Holland, P.W., Leinhardt, S.: Transitivity in structural models of small groups. Small Group Res. 2(2), 107\u2013124 (1971)","journal-title":"Small Group Res."},{"key":"6_CR22","first-page":"P05031","volume":"2011","author":"D Jin","year":"2011","unstructured":"Jin, D., Yang, B., Baquero, C., Liu, D., He, D., Liu, J.: A markov random walk under constraint for discovering overlapping communities in complex networks. J. Stat. Mech. Theory Exp. 2011, P05031 (2011)","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"033015","DOI":"10.1088\/1367-2630\/11\/3\/033015","volume":"11","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti, A., Fortunato, S., Kert\u00e9sz, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11, 033015 (2009)","journal-title":"New J. Phys."},{"issue":"4","key":"6_CR24","doi-asserted-by":"publisher","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","volume":"78","author":"A Lancichinetti","year":"2008","unstructured":"Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E (Stat. Nonlin. Soft Matter Phys.) 78(4), 046110 (2008)","journal-title":"Phys. Rev. E (Stat. Nonlin. Soft Matter Phys.)"},{"doi-asserted-by":"crossref","unstructured":"Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PLoS One 6(5)","key":"6_CR25","DOI":"10.1371\/journal.pone.0018961"},{"doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web. ACM (2010)","key":"6_CR26","DOI":"10.1145\/1772690.1772756"},{"issue":"1","key":"6_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec, J., Kleinberg, J.M., Faloutsos, C.: Graph evolution: densification and shrinking diameters. TKDD 1(1), 1\u201340 (2007)","journal-title":"TKDD"},{"issue":"4","key":"6_CR28","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","volume":"54","author":"D Lusseau","year":"2003","unstructured":"Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396\u2013405 (2003)","journal-title":"Behav. Ecol. Sociobiol."},{"key":"6_CR29","volume-title":"Computing with Social Trust","author":"P Massa","year":"2009","unstructured":"Massa, P., Avesani, P.: Trust metrics in recommender systems. In: Golbeck, J. (ed.) Computing with Social Trust. Springer, London (2009)"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"16107","DOI":"10.1103\/PhysRevE.77.016107","volume":"77","author":"T Nepusz","year":"2008","unstructured":"Nepusz, T., Petr\u00f3czi, A., N\u00e9gyessy, L., Bazs\u00f3, F.: Fuzzy communities and the concept of bridgeness in complex networks. Phys. Rev. E 77(1), 16107 (2008)","journal-title":"Phys. Rev. E"},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"M Newman","year":"2004","unstructured":"Newman, M., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)","journal-title":"Phys. Rev. E"},{"key":"6_CR32","doi-asserted-by":"publisher","first-page":"P03024","DOI":"10.1088\/1742-5468\/2009\/03\/P03024","volume":"2009","author":"V Nicosia","year":"2009","unstructured":"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, P03024 (2009)","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/11569596_31","volume-title":"Computer and Information Sciences - ISCIS 2005","author":"P Pons","year":"2005","unstructured":"Pons, P., Latapy, M.: Computing communities in large networks using random walks. In: Yolum, I., G\u00fcng\u00f6r, T., G\u00fcrgen, F., \u00d6zturan, C. (eds.) ISCIS 2005. LNCS, vol. 3733, pp. 284\u2013293. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Prat-P\u00e9rez, 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, CIKM 2012. ACM (2012)","key":"6_CR34","DOI":"10.1145\/2396761.2398496"},{"key":"6_CR35","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1073\/pnas.0706851105","volume":"105","author":"M Rosvall","year":"2008","unstructured":"Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Nat. Acad. Sci. U.S.A. 105, 1118\u20131123 (2008)","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"issue":"1","key":"6_CR36","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27\u201364 (2007)","journal-title":"Comput. Sci. Rev."},{"unstructured":"SNAP. http:\/\/snap.stanford.edu\/data","key":"6_CR37"},{"key":"6_CR38","first-page":"404","volume":"1","author":"Y Song","year":"2013","unstructured":"Song, Y., Bressan, S.: Fast community detection. DEXA 1, 404\u2013418 (2013)","journal-title":"DEXA"},{"unstructured":"TrustLet. http:\/\/www.trustlet.org\/","key":"6_CR39"},{"unstructured":"van Dongen, S.M.: Graph clustering by flow simulation. Ph.D. thesis, University of Utrecht (2000)","key":"6_CR40"},{"issue":"6684","key":"6_CR41","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 409\u2013410 (1998)","journal-title":"Nature"},{"issue":"4","key":"6_CR42","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/2501654.2501657","volume":"45","author":"J Xie","year":"2013","unstructured":"Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv. 45(4), 43:1\u201343:35 (2013)","journal-title":"ACM Comput. Surv."},{"key":"6_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-30220-6_3","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"J Xie","year":"2012","unstructured":"Xie, J., Szymanski, B.K.: Towards linear time overlapping community detection in social networks. In: Tan, P.-N., Chawla, S., Ho, C.K., Bailey, J. (eds.) PAKDD 2012, Part II. LNCS, vol. 7302, pp. 25\u201336. Springer, Heidelberg (2012)"},{"unstructured":"Yan, B., Gregory, S.: Detecting communities in networks by merging cliques. CoRR (2012)","key":"6_CR44"},{"doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS 2012. ACM (2012)","key":"6_CR45","DOI":"10.1145\/2350190.2350193"},{"doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Overlapping community detection at scale: a nonnegative matrix factorization approach. In: WSDM (2013)","key":"6_CR46","DOI":"10.1145\/2433396.2433471"},{"unstructured":"Yen, L., Vanvyve, L., Wouters, D., Fouss, F., Verleysen, F., Saerens, M.: Clustering using a random-walk based distance measure. In: Proceedings of ESANN\u20192005 (2005)","key":"6_CR47"},{"issue":"1","key":"6_CR48","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1016\/j.physa.2006.07.023","volume":"374","author":"S Zhang","year":"2007","unstructured":"Zhang, S., Wang, R.S., Zhang, X.S.: Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Phys. A 374(1), 483\u2013490 (2007)","journal-title":"Phys. A"},{"doi-asserted-by":"crossref","unstructured":"Zhang, Z.-Y., Wang, Y., Ahn, Y.-Y.: Overlapping community detection in complex networks using symmetric binary matrix factorization. CoRR (2013)","key":"6_CR49","DOI":"10.1103\/PhysRevE.87.062803"}],"container-title":["Lecture Notes in Computer Science","Transactions on Large-Scale Data- and Knowledge-Centered Systems XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46485-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T04:18:13Z","timestamp":1676434693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-46485-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662464847","9783662464854"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46485-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"22 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}