{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:50:11Z","timestamp":1756572611346,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2018AAA0101902"],"award-info":[{"award-number":["2018AAA0101902"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61532001"],"award-info":[{"award-number":["61532001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MOE-ChinaMobile Program","award":["MCM20170503"],"award-info":[{"award-number":["MCM20170503"]}]},{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2014CB340405"],"award-info":[{"award-number":["2014CB340405"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Trans. Soc. Comput."],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>Community detection is a hot topic for researchers in the fields of graph theory, social networks, and biological networks. Generally speaking, a community refers to a group of densely linked nodes in the network. Nodes usually have more than one community label, indicating their multiple roles or functions in the network. Unfortunately, existing solutions aiming at overlapping community detection are not capable of scaling to large-scale networks with millions of nodes and edges. In this article, we propose a fast-overlapping-community-detection algorithm\u2014FOX. In the experiment on a network with 3.9 millions nodes and 20 millions edges, the detection finishes in 41 min and provides the most qualified results. The second-fastest algorithm, however, takes almost five times longer to run. As for another network with 22 millions nodes and 127 millions edges, our algorithm is the only one that can provide an overlapping community detection result and it only takes 533 min. Our algorithm is a typical heuristic algorithm, measuring the closeness of a node to a community by counting the number of triangles formed by the node and two other nodes in the community. We also extend the exploitation of triangle to open-triangle, which enlarges the scale of the detected communities.<\/jats:p>","DOI":"10.1145\/3404970","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T23:23:48Z","timestamp":1596497028000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["FOX"],"prefix":"10.1145","volume":"3","author":[{"given":"Tianshu","family":"Lyu","sequence":"first","affiliation":[{"name":"Department of Machine Intelligence, Peking University"}]},{"given":"Lidong","family":"Bing","sequence":"additional","affiliation":[{"name":"DAMO Academy, Alibaba Group"}]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Kwai Inc."}]},{"given":"Yan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Machine Intelligence, Peking University"}]}],"member":"320","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl039"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670323"},{"key":"e_1_2_1_3_1","unstructured":"Radhika Arava. 2015. An efficient homophilic model and algorithms for community detection using Nash dynamics. arXiv preprint arXiv:1506.05659.  Radhika Arava. 2015. An efficient homophilic model and algorithms for community detection using Nash dynamics. arXiv preprint arXiv:1506.05659."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Susan Athey Emilio Calvano and Saumitra Jha. 2016. A theory of community formation and social hierarchy. CSEF Working Papers Centre for Studies in Economics and Finance (CSEF) University of Naples Italy. https:\/\/ideas.repec.org\/p\/sef\/csefwp\/451.html.  Susan Athey Emilio Calvano and Saumitra Jha. 2016. A theory of community formation and social hierarchy. CSEF Working Papers Centre for Studies in Economics and Finance (CSEF) University of Naples Italy. https:\/\/ideas.repec.org\/p\/sef\/csefwp\/451.html.","DOI":"10.2139\/ssrn.2823777"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132925"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0186-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-2909.116.3.457"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2797115.2797131"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398792"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1221839110"},{"volume-title":"Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 427--436","author":"Hou Yangyang","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_14_1","unstructured":"Stephen Kelley. 2009. The Existence and Discovery of Overlapping Communities in Large-scale Networks. Rensselaer Polytechnic Institute.  Stephen Kelley. 2009. The Existence and Discovery of Overlapping Communities in Large-scale Networks. Rensselaer Polytechnic Institute."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.026109"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-014-0401-1"},{"key":"e_1_2_1_19_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"volume-title":"Proceedings of the IEEE 16th International Conference on Data Mining (ICDM). 1071--1076","author":"Lyu T.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 21st International Conference on Pattern Recognition (ICPR\u201912)","author":"Narayanam R.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2009\/03\/P03024"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Gergely Palla Albert-L\u00e1szl\u00f3 Barab\u00e1si and Tam\u00e1s Vicsek. 2007. Quantifying social group evolution. Nature 446 7136 (2007) 664--667.  Gergely Palla Albert-L\u00e1szl\u00f3 Barab\u00e1si and Tam\u00e1s Vicsek. 2007. Quantifying social group evolution. Nature 446 7136 (2007) 664--667.","DOI":"10.1038\/nature05670"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1057\/ejis.2010.15"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398496"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568010"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1177\/0146167294205005"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476440"},{"volume-title":"Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM\u201910)","author":"Rees B. S.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1177\/0170840607076007"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2744715"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.056128"},{"key":"e_1_2_1_37_1","unstructured":"Thomas Schank. 2007. Algorithmic Aspects of Triangle-Based Network Analysis. Universit\u00e4t Karlsruhe Karlsruhe. 10.5445\/IR\/1000007159  Thomas Schank. 2007. Algorithmic Aspects of Triangle-Based Network Analysis. Universit\u00e4t Karlsruhe Karlsruhe. 10.5445\/IR\/1000007159"},{"volume-title":"Proceedings of the SIAM International Conference on Data Mining. SIAM, 10--18","author":"Seshadhri Comandur","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783301"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2013.05.004"},{"volume-title":"Transactions on","author":"Song Yi","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433461"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794370"},{"volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence.","year":"2017","author":"Wang Xiao","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518687"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518687"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2017.2711038"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2017.2749282"},{"volume-title":"Data Science","author":"Zhou Lihua","key":"e_1_2_1_52_1"}],"container-title":["ACM Transactions on Social Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404970","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3404970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:45Z","timestamp":1750191465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404970"}},"subtitle":["Fast Overlapping Community Detection Algorithm\u00a0in Big Weighted Networks"],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3404970"],"URL":"https:\/\/doi.org\/10.1145\/3404970","relation":{},"ISSN":["2469-7818","2469-7826"],"issn-type":[{"type":"print","value":"2469-7818"},{"type":"electronic","value":"2469-7826"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}