{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:28:35Z","timestamp":1763641715477},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> The community structure detection is an important problem in many areas such as biology network, computer network and social network. The objective of this problem is to analyze the relationships among data via the network topology. In the literature, many works have been done for partitioning a network into communities or clustering data into groups. In this paper, we define a series of conditions for communities and formulate the community detection problem into a combinatorial optimization problem which aims at partitioning a given network into disjoint communities such that all the communities satisfy the community conditions. We show that the maximization version of this problem is [Formula: see text]-hard for general networks under some natural conditions, and we develop a greedy heuristic algorithm for it. We also develop a refine algorithm to improve the modularity score of a community partition, subject to the community conditions. <\/jats:p>","DOI":"10.1142\/s1793830913500316","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T02:10:16Z","timestamp":1378174216000},"page":"1350031","source":"Crossref","is-referenced-by-count":5,"title":["THE MAXIMUM COMMUNITY PARTITION PROBLEM IN NETWORKS"],"prefix":"10.1142","volume":"05","author":[{"given":"ZAIXIN","family":"LU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WEILI","family":"WU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WEIDONG","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, South China Normal University, Guangzhou, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIAOFEI","family":"ZHONG","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Central Missouri, Warrensburg, Missouri 64093, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YUANJUN","family":"BI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ZHENG","family":"GAO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,12,3]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.2307\/2088670"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"},{"key":"rf6","volume-title":"The Stanford Graph Base: A Platform for Combinatorial Computing","author":"Knuth D. E.","year":"1993"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00265-003-0651-y"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190689"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.026121"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.77.036109"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9356-0"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31955-9_8"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.118703"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830913500316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:13:41Z","timestamp":1565115221000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830913500316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":22,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2013,12,3]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S1793830913500316"],"URL":"https:\/\/doi.org\/10.1142\/s1793830913500316","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}