Overlapping Community Detection Using Multiobjective Genetic Algorithm
| Autor: | Amit Kumar, Nirmalya Chowdhury, Ritam Sarkar, Debaditya Barman |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Modularity (networks) education.field_of_study Optimization problem Population Crossover 02 engineering and technology 01 natural sciences 010305 fluids & plasmas Human-Computer Interaction Parameter identification problem Chromosome (genetic algorithm) Modeling and Simulation 0103 physical sciences Genetic algorithm Mutation (genetic algorithm) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing education Social Sciences (miscellaneous) |
| Zdroj: | IEEE Transactions on Computational Social Systems. 7:802-817 |
| ISSN: | 2373-7476 |
| DOI: | 10.1109/tcss.2020.2989295 |
| Popis: | Community detection or identification problem has emerged as an important task in the field of network analysis. The problem becomes more challenging when the communities overlap each other. Since the community detection problem can be modeled as an optimization problem, the genetic algorithm (GA) can be used to develop a solution. Typically, overlapping community detection problem is a multiobjective optimization problem and there may exist some conflicts among these objectives. Therefore, a simple GA-based solution is not efficient for detecting overlapping communities in a social network. For this purpose, we have proposed an overlapping community detection method based on nondominated sorting GA (NSGA)-II having two objective functions. The first objective function maximizes internal link density within the community using fuzzy membership values while the second objective function minimizes the external link density of the communities. The initial population has been created based on the neighbors. A mutation operator has been proposed in this article to restrict the randomness in the chromosome. An updation operator has also been proposed to modify a chromosome after crossover and mutation operation. The proposed method can handle different network structures properly. In order to show the effectiveness, the proposed method has been compared with some popular methods on several real-world environments in terms of two performance measurement techniques, namely, generalized normalized mutual information (gNMI) and extended modularity ( $Q_{\text {ov}}$ ). The empirical results reveal that our proposed method has succeeded to obtain better gNMI and comparable extended modularity values. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|