Lu, Zaixin; Wu, Weili; Chen, Weidong; Zhong, Jiaofei; Bi, Yuanjun; Gao, Zheng The maximum community partition problem in networks. (English) Zbl 1285.90053 Discrete Math. Algorithms Appl. 5, No. 4, Article ID 1350031, 16 p. (2013). Summary: 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 \(\mathcal{NP}\)-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. Cited in 1 Document MSC: 90C27 Combinatorial optimization 90B10 Deterministic network models in operations research Keywords:community partition; \(\mathcal{NP}\)-hard PDFBibTeX XMLCite \textit{Z. Lu} et al., Discrete Math. Algorithms Appl. 5, No. 4, Article ID 1350031, 16 p. (2013; Zbl 1285.90053) Full Text: DOI References: [1] DOI: 10.1007/978-1-4612-0619-4 · doi:10.1007/978-1-4612-0619-4 [2] DOI: 10.2307/2088670 · doi:10.2307/2088670 [3] DOI: 10.1145/990308.990313 · Zbl 1192.05160 · doi:10.1145/990308.990313 [4] DOI: 10.1086/jar.33.4.3629752 · doi:10.1086/jar.33.4.3629752 [5] Knuth D. E., The Stanford Graph Base: A Platform for Combinatorial Computing (1993) · Zbl 0806.68121 [6] DOI: 10.1073/pnas.122653799 · Zbl 1032.91716 · doi:10.1073/pnas.122653799 [7] DOI: 10.1007/s00265-003-0651-y · doi:10.1007/s00265-003-0651-y [8] DOI: 10.1103/PhysRevE.69.066133 · doi:10.1103/PhysRevE.69.066133 [9] DOI: 10.1103/PhysRevE.70.066111 · doi:10.1103/PhysRevE.70.066111 [10] DOI: 10.1073/pnas.0400054101 · doi:10.1073/pnas.0400054101 [11] DOI: 10.1103/PhysRevE.69.026113 · doi:10.1103/PhysRevE.69.026113 [12] DOI: 10.1103/PhysRevE.74.036104 · doi:10.1103/PhysRevE.74.036104 [13] DOI: 10.1073/pnas.0605965104 · doi:10.1073/pnas.0605965104 [14] DOI: 10.1109/TKDE.2007.190689 · Zbl 05340199 · doi:10.1109/TKDE.2007.190689 [15] DOI: 10.1103/PhysRevE.78.026121 · doi:10.1103/PhysRevE.78.026121 [16] DOI: 10.1103/PhysRevE.77.036109 · doi:10.1103/PhysRevE.77.036109 [17] DOI: 10.1016/j.physrep.2009.11.002 · doi:10.1016/j.physrep.2009.11.002 [18] DOI: 10.1007/s10878-010-9356-0 · Zbl 1245.90013 · doi:10.1007/s10878-010-9356-0 [19] DOI: 10.1007/978-3-540-31955-9_8 · doi:10.1007/978-3-540-31955-9_8 [20] DOI: 10.1103/PhysRevE.80.056117 · doi:10.1103/PhysRevE.80.056117 [21] DOI: 10.1016/j.cosrev.2007.05.001 · Zbl 1302.68237 · doi:10.1016/j.cosrev.2007.05.001 [22] DOI: 10.1103/PhysRevLett.100.118703 · doi:10.1103/PhysRevLett.100.118703 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.