Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks
Community structure is one of the most important properties in social networks. In dynamic networks, there are two conflicting criteria that need to be considered. One is the snapshot quality, which evaluates the quality of the community partitions at the current time step. The other is the temporal...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/402345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850230130074451968 |
|---|---|
| author | Jingjing Ma Jie Liu Wenping Ma Maoguo Gong Licheng Jiao |
| author_facet | Jingjing Ma Jie Liu Wenping Ma Maoguo Gong Licheng Jiao |
| author_sort | Jingjing Ma |
| collection | DOAJ |
| description | Community structure is one of the most important properties in social networks. In dynamic networks, there are two conflicting criteria that need to be considered. One is the snapshot quality, which evaluates the quality of the community partitions at the current time step. The other is the temporal cost, which evaluates the difference between communities at different time steps. In this paper, we propose a decomposition-based multiobjective community detection algorithm to simultaneously optimize these two objectives to reveal community structure and its evolution in dynamic networks. It employs the framework of multiobjective evolutionary algorithm based on decomposition to simultaneously optimize the modularity and normalized mutual information, which quantitatively measure the quality of the community partitions and temporal cost, respectively. A local search strategy dealing with the problem-specific knowledge is incorporated to improve the effectiveness of the new algorithm. Experiments on computer-generated and real-world networks demonstrate that the proposed algorithm can not only find community structure and capture community evolution more accurately, but also be steadier than the two compared algorithms. |
| format | Article |
| id | doaj-art-2a07a9db9845437a8ac94fa237d9cb17 |
| institution | OA Journals |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-2a07a9db9845437a8ac94fa237d9cb172025-08-20T02:03:58ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/402345402345Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social NetworksJingjing Ma0Jie Liu1Wenping Ma2Maoguo Gong3Licheng Jiao4Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaCommunity structure is one of the most important properties in social networks. In dynamic networks, there are two conflicting criteria that need to be considered. One is the snapshot quality, which evaluates the quality of the community partitions at the current time step. The other is the temporal cost, which evaluates the difference between communities at different time steps. In this paper, we propose a decomposition-based multiobjective community detection algorithm to simultaneously optimize these two objectives to reveal community structure and its evolution in dynamic networks. It employs the framework of multiobjective evolutionary algorithm based on decomposition to simultaneously optimize the modularity and normalized mutual information, which quantitatively measure the quality of the community partitions and temporal cost, respectively. A local search strategy dealing with the problem-specific knowledge is incorporated to improve the effectiveness of the new algorithm. Experiments on computer-generated and real-world networks demonstrate that the proposed algorithm can not only find community structure and capture community evolution more accurately, but also be steadier than the two compared algorithms.http://dx.doi.org/10.1155/2014/402345 |
| spellingShingle | Jingjing Ma Jie Liu Wenping Ma Maoguo Gong Licheng Jiao Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks The Scientific World Journal |
| title | Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks |
| title_full | Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks |
| title_fullStr | Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks |
| title_full_unstemmed | Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks |
| title_short | Decomposition-Based Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Social Networks |
| title_sort | decomposition based multiobjective evolutionary algorithm for community detection in dynamic social networks |
| url | http://dx.doi.org/10.1155/2014/402345 |
| work_keys_str_mv | AT jingjingma decompositionbasedmultiobjectiveevolutionaryalgorithmforcommunitydetectionindynamicsocialnetworks AT jieliu decompositionbasedmultiobjectiveevolutionaryalgorithmforcommunitydetectionindynamicsocialnetworks AT wenpingma decompositionbasedmultiobjectiveevolutionaryalgorithmforcommunitydetectionindynamicsocialnetworks AT maoguogong decompositionbasedmultiobjectiveevolutionaryalgorithmforcommunitydetectionindynamicsocialnetworks AT lichengjiao decompositionbasedmultiobjectiveevolutionaryalgorithmforcommunitydetectionindynamicsocialnetworks |