{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T00:21:16Z","timestamp":1722039676027},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Most of the community detection algorithms assume that the<jats:italic>complete<\/jats:italic>network structure<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}=(\\mathcal {V},\\mathcal {E})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>G<\/mml:mi><mml:mo>=<\/mml:mo><mml:mo>(<\/mml:mo><mml:mi>V<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>E<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is available in advance for analysis. However, in reality this may not be true due to several reasons, such as privacy constraints and restricted access, which result in a partial snapshot of the entire network. In addition, we may be interested in identifying the community information of only a selected subset of nodes (denoted by<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {V}_{{\\mathrm{T}}} \\subseteq \\mathcal {V}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>V<\/mml:mi><mml:mi>T<\/mml:mi><\/mml:msub><mml:mo>\u2286<\/mml:mo><mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>), rather than obtaining the community structure of all the nodes in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. To this end, we propose an incremental community detection method that repeats two stages\u2014(i) network scan and (ii) community update. In the first stage, our method selects an appropriate node in such a way that the discovery of its local neighborhood structure leads to an accurate community detection in the second stage. We propose a novel criterion, called<jats:italic>Information Gain<\/jats:italic>, based on existing network embedding algorithms (Deepwalk and node2vec) to scan a node. The proposed community update stage consists of expectation\u2013maximization and Markov Random Field-based denoising strategy. Experiments with 5 diverse networks with known ground-truth community structure show that our algorithm achieves 10.2% higher accuracy on average over state-of-the-art algorithms for both network scan and community update steps.<\/jats:p>","DOI":"10.1007\/s10115-019-01422-6","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T03:02:01Z","timestamp":1573786921000},"page":"2281-2300","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Incremental community discovery via latent network representation and probabilistic inference"],"prefix":"10.1007","volume":"62","author":[{"given":"Zhe","family":"Cui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noseong","family":"Park","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanmoy","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"issue":"3","key":"1422_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486(3):75\u2013174","journal-title":"Phys Rep"},{"issue":"2","key":"1422_CR2","doi-asserted-by":"publisher","first-page":"026132","DOI":"10.1103\/PhysRevE.72.026132","volume":"72","author":"A Clauset","year":"2005","unstructured":"Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132","journal-title":"Phys Rev E"},{"issue":"4","key":"1422_CR3","doi-asserted-by":"publisher","first-page":"387","DOI":"10.3233\/WIA-2008-0147","volume":"6","author":"F Luo","year":"2008","unstructured":"Luo F, Wang JZ, Promislow E (2008) Exploring local community structures in large networks. Web Intell Agent Syst Int J 6(4):387\u2013400","journal-title":"Web Intell Agent Syst Int J"},{"issue":"10","key":"1422_CR4","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008","journal-title":"J Stat Mech Theory Exp"},{"key":"1422_CR5","doi-asserted-by":"crossref","unstructured":"Kim M, Leskovec J (2011) The network completion problem: Inferring missing nodes and edges in networks. In: Proceedings of the 2011 SIAM international conference on data mining, pp 47\u201358","DOI":"10.1137\/1.9781611972818.5"},{"key":"1422_CR6","doi-asserted-by":"publisher","first-page":"036103","DOI":"10.1103\/PhysRevE.84.036103","volume":"84","author":"B Ball","year":"2011","unstructured":"Ball B, Karrer B, Newman MEJ (2011) Efficient and principled method for detecting communities in networks. Phys Rev E 84:036103","journal-title":"Phys Rev E"},{"key":"1422_CR7","volume-title":"Pattern recognition and machine learning","author":"CM Bishop","year":"2006","unstructured":"Bishop CM (2006) Pattern recognition and machine learning. Springer, Berlin"},{"key":"1422_CR8","doi-asserted-by":"crossref","unstructured":"Liu J, Aggarwal C, Han J (2015) On integrating network and community discovery. In: WSDM, Shanghai, China, pp 117\u2013126","DOI":"10.1145\/2684822.2685323"},{"issue":"2","key":"1422_CR9","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/2953883","volume":"11","author":"T Chakraborty","year":"2016","unstructured":"Chakraborty T, Srinivasan S, Ganguly N, Mukherjee A, Bhowmick S (2016) Permanence and community structure in complex networks. ACM Trans Knowl Discov Data 11(2):14:1\u201314:34","journal-title":"ACM Trans Knowl Discov Data"},{"issue":"4","key":"1422_CR10","doi-asserted-by":"publisher","first-page":"54:1","DOI":"10.1145\/3091106","volume":"50","author":"T Chakraborty","year":"2017","unstructured":"Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv 50(4):54:1\u201354:37","journal-title":"ACM Comput Surv"},{"key":"1422_CR11","doi-asserted-by":"crossref","unstructured":"Nassar H, Kloster K, Gleich DF (2015) Strong localization in personalized PageRank vectors. In: International workshop on algorithms and models for the web-graph. Springer, pp 190\u2013202","DOI":"10.1007\/978-3-319-26784-5_15"},{"key":"1422_CR12","doi-asserted-by":"crossref","unstructured":"Yin H, Benson AR, Leskovec J, Gleich DF (2017) Local higher-order graph clustering. In: ACM Conference on knowledge discovery and data mining, pp 555\u2013564","DOI":"10.1145\/3097983.3098069"},{"issue":"12","key":"1422_CR13","doi-asserted-by":"publisher","first-page":"2274","DOI":"10.1109\/TCYB.2014.2357896","volume":"44","author":"C Liu","year":"2014","unstructured":"Liu C, Liu J, Jiang Z (2014) A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks. IEEE Trans Cybern 44(12):2274\u20132287","journal-title":"IEEE Trans Cybern"},{"key":"1422_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.physa.2016.11.036","volume":"471","author":"X Wang","year":"2017","unstructured":"Wang X, Liu J (2017) A layer reduction based community detection algorithm on multiplex networks. Physica A 471:244\u2013252","journal-title":"Physica A"},{"key":"1422_CR15","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.physa.2015.12.126","volume":"449","author":"Z Li","year":"2016","unstructured":"Li Z, Liu J (2016) A multi-agent genetic algorithm for community detection in complex networks. Physica A 449:336\u2013347","journal-title":"Physica A"},{"key":"1422_CR16","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Kumar R, Tomkins A (2006) Evolutionary clustering. In: ACM Conference on knowledge discovery and data mining, pp 554\u2013560","DOI":"10.1145\/1150402.1150467"},{"key":"1422_CR17","doi-asserted-by":"crossref","unstructured":"Zhang J, Yu PS (2015) Community detection for emerging networks. In: Proceedings of the 2015 SIAM international conference on data mining, Vancouver, Canada, pp 127\u2013135","DOI":"10.1137\/1.9781611974010.15"},{"issue":"99","key":"1422_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TSMC.2018.2868069","volume":"99","author":"J Cheng","year":"2018","unstructured":"Cheng J, Wu X, Zhou M, Gao S, Huang Z, Liu C (2018) A novel method for detecting new overlapping community in complex evolving networks. IEEE Trans Syst Man Cybern Syst 99(99):1\u201313","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"issue":"4","key":"1422_CR19","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1109\/TSMC.2013.2256890","volume":"44","author":"Z Wang","year":"2014","unstructured":"Wang Z, Zhang D, Zhou X, Yang D, Yu Z, Yu Z (2014) Discovering and profiling overlapping communities in location-based social networks. IEEE Trans Syst Man Cybern Syst 44(4):499\u2013509","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"key":"1422_CR20","doi-asserted-by":"crossref","unstructured":"Lin W, Kong X, Yu PS, Wu Q, Jia Y, Li C (2012) Community detection in incomplete information networks. In: International conference on world wide web. Lyon, France, pp 341\u2013350","DOI":"10.1145\/2187836.2187883"},{"issue":"3","key":"1422_CR21","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/s10878-014-9719-z","volume":"28","author":"L Wang","year":"2014","unstructured":"Wang L, Wang J, Bi Y, Wu W, Xu W, Lian B (2014) Noise-tolerance community detection and evolution in dynamic social networks. J Comb Optim 28(3):600\u2013612","journal-title":"J Comb Optim"},{"key":"1422_CR22","doi-asserted-by":"crossref","unstructured":"Koujaku S, Kudo M, Takigawa I, Imai H (2015) Community change detection in dynamic networks in noisy environment. In: Proceedings of the international conference on World Wide Web, pp 793\u2013798","DOI":"10.1145\/2740908.2742471"},{"key":"1422_CR23","doi-asserted-by":"crossref","unstructured":"Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: International conference on knowledge discovery and data mining, pp 631\u2013636","DOI":"10.1145\/1150402.1150479"},{"issue":"2","key":"1422_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601438","volume":"8","author":"NK Ahmed","year":"2014","unstructured":"Ahmed NK, Neville J, Kompella R (2014) Network sampling: from static to streaming graphs. ACM Trans Knowl Discov Data 8(2):1\u201356","journal-title":"ACM Trans Knowl Discov Data"},{"issue":"1","key":"1422_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2435215.2435218","volume":"7","author":"E Baykan","year":"2013","unstructured":"Baykan E, Henzinger M, Weber I (2013) A comprehensive study of techniques for url-based web page language classification. ACM Trans Web 7(1):1\u201337","journal-title":"ACM Trans Web"},{"issue":"4","key":"1422_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/2740070.2631452","volume":"44","author":"M Gabielkov","year":"2014","unstructured":"Gabielkov M, Rao A, Legout A (2014) Sampling online social networks: an experimental study of twitter. ACM Comput Commun Rev 44(4):127\u2013128","journal-title":"ACM Comput Commun Rev"},{"key":"1422_CR27","doi-asserted-by":"crossref","unstructured":"Lu J, Li D (2012) Sampling online social networks by random walk. In: International workshop on hot topics on interdisciplinary social networks research, pp 33\u201340","DOI":"10.1145\/2392622.2392628"},{"key":"1422_CR28","unstructured":"Yun S-Y, Proutiere A (2014) Community detection via random and adaptive sampling. In: Conference on learning theory, pp 138\u2013175"},{"issue":"8","key":"1422_CR29","first-page":"2339","volume":"13","author":"MW Mahoney","year":"2012","unstructured":"Mahoney MW, Orecchia L, Vishnoi NK (2012) A local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally. J Mach Learn Res 13(8):2339\u20132365","journal-title":"J Mach Learn Res"},{"key":"1422_CR30","first-page":"1873504","volume":"2016","author":"F Meng","year":"2016","unstructured":"Meng F, Zhang F, Zhu M, Xing Y, Wang Z, Shi J (2016) Incremental density-based link clustering algorithm for community detection in dynamic networks. Math Prob Eng 2016:1873504","journal-title":"Math Prob Eng"},{"key":"1422_CR31","doi-asserted-by":"crossref","unstructured":"Xie J, Chen M, Szymanski BK (2013) Labelrankt: incremental community detection in dynamic networks via label propagation. In: Proceedings of the workshop on dynamic networks management and mining, pp 25\u201332","DOI":"10.1145\/2489247.2489249"},{"key":"1422_CR32","doi-asserted-by":"crossref","unstructured":"Takaffoli M, Rabbany R, Za\u00efane OR (2013) 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, pp 90\u201394","DOI":"10.1145\/2492517.2492633"},{"key":"1422_CR33","unstructured":"Zakrzewska A, Bader DA (2015) Fast incremental community detection on dynamic graphs. In: International conference on parallel processing and applied mathematics, pp 207\u2013217"},{"key":"1422_CR34","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.tcs.2014.11.026","volume":"584","author":"A Clementi","year":"2015","unstructured":"Clementi A, Di Ianni M, Gambosi G, Natale E, Silvestri R (2015) Distributed community detection in dynamic graphs. Theor Comput Sci 584:19\u201341","journal-title":"Theor Comput Sci"},{"key":"1422_CR35","unstructured":"Becchetti L, Clementi A, Natale E, Pasquale F, Trevisan L (2017) Find your place: simple distributed algorithms for community detection. In: Proceedings of the 28th annual ACM SIAM symposium on discrete algorithms, pp 940\u2013959"},{"key":"1422_CR36","unstructured":"Ng AY, Jordan MI, Weiss Y (2001) On spectral clustering: analysis and an algorithm. In: Advances in neural information processing systems. Vancouver, British Columbia, Canada, pp 849\u2013856"},{"key":"1422_CR37","doi-asserted-by":"crossref","unstructured":"Nguyen NP, Dinh TN, Xuan Y, Thai MT (2011) Adaptive algorithms for detecting community structure in dynamic social networks. In: IEEE International conference on computer communications, pp 2282\u20132290","DOI":"10.1109\/INFCOM.2011.5935045"},{"key":"1422_CR38","doi-asserted-by":"crossref","unstructured":"Agarwal P, Verma R, Agarwal A, Chakraborty T (2018) Dyperm: maximizing permanence for dynamic community detection. In Pacific-asia conference on advances in knowledge discovery and data mining (PAKDD), pp 437\u2013449","DOI":"10.1007\/978-3-319-93034-3_35"},{"key":"1422_CR39","doi-asserted-by":"crossref","unstructured":"Li X, Wu B, Guo Q, Zeng X, Shi C (2015) Dynamic community detection algorithm based on incremental identification. In: 2015 IEEE International conference on data mining workshop, pp 900\u2013907","DOI":"10.1109\/ICDMW.2015.158"},{"key":"1422_CR40","doi-asserted-by":"crossref","unstructured":"Soundarajan S, Eliassi-Rad T, Gallagher B, Pinar A (2016) Maxreach: reducing network incompleteness through node probes. In: ASONAM, San Fransisco, CA, USA, pp 152\u2013157","DOI":"10.1109\/ASONAM.2016.7752227"},{"issue":"1","key":"1422_CR41","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter JS (1985) Random sampling with a reservoir. ACM Trans Math Softw (TOMS) 11(1):37\u201357","journal-title":"ACM Trans Math Softw (TOMS)"},{"key":"1422_CR42","doi-asserted-by":"crossref","unstructured":"Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. In: SIGKDD, New York, USA, pp 701\u2013710","DOI":"10.1145\/2623330.2623732"},{"key":"1422_CR43","doi-asserted-by":"crossref","unstructured":"Grover A, Leskovec J (2016) Node2vec: scalable feature learning for networks. In: SIGKDD, San Francisco, CA, USA, pp 855\u2013864","DOI":"10.1145\/2939672.2939754"},{"key":"1422_CR44","unstructured":"Mikolov T, Chen K, Corrado G, Dean J (2013) Efficient estimation of word representations in vector space, CoRR, arXiv:1301.3781"},{"key":"1422_CR45","doi-asserted-by":"crossref","unstructured":"Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) Line: large-scale information network embedding. In: WWW, Florence, Italy, pp 1067\u20131077","DOI":"10.1145\/2736277.2741093"},{"key":"1422_CR46","doi-asserted-by":"crossref","unstructured":"Chang S, Han W, Tang J, Qi G-J, Aggarwal CC, Huang TS (2015) Heterogeneous network embedding via deep architectures In: SIGKDD, Sydney, Australia, pp 119\u2013128","DOI":"10.1145\/2783258.2783296"},{"key":"1422_CR47","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-642-30287-9_10","volume-title":"Complex networks","author":"M Seifi","year":"2013","unstructured":"Seifi M, Junier I, Rouquier J-B, Iskrov S, Guillaume J-L (2013) Stable community cores in complex networks. In: Menezes R, Evsukoff A, Gonz\u00e1lez MC (eds) Complex networks. Springer, Berlin, Heidelberg, pp 87\u201398"},{"key":"1422_CR48","doi-asserted-by":"crossref","unstructured":"Chakraborty T, Srinivasan S, Ganguly N, Mukherjee A, Bhowmick S (2014) On the permanence of vertices in network communities. In: Proceedings of international conference on knowledge discovery and data mining, pp 1396\u20131405","DOI":"10.1145\/2623330.2623707"},{"issue":"2","key":"1422_CR49","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.patrec.2009.09.023","volume":"31","author":"W Khreich","year":"2010","unstructured":"Khreich W, Granger E, Miri A, Sabourin R (2010) On the memory complexity of the forward\u2013backward algorithm. Pattern Recogn Lett 31(2):91\u201399","journal-title":"Pattern Recogn Lett"},{"issue":"3","key":"1422_CR50","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1111\/j.2517-6161.1986.tb01412.x","volume":"48","author":"J Besag","year":"1986","unstructured":"Besag J (1986) On the statistical analysis of dirty pictures. J R Stat Soc. Ser B (Methodol) 48(3):259\u2013302","journal-title":"J R Stat Soc. Ser B (Methodol)"},{"key":"1422_CR51","doi-asserted-by":"publisher","first-page":"016118","DOI":"10.1103\/PhysRevE.80.016118","volume":"80","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80:016118","journal-title":"Phys Rev E"},{"key":"1422_CR52","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: stanford large network dataset collection, http:\/\/snap.stanford.edu\/data. Accessed May 2018"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01422-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-019-01422-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01422-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T23:35:57Z","timestamp":1722036957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-019-01422-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["1422"],"URL":"https:\/\/doi.org\/10.1007\/s10115-019-01422-6","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"8 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}