×

The maximum community partition problem in networks. (English) Zbl 1285.90053

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.

MSC:

90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
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.