A Dynamic Method to Adjust Overlapping Community Structures

Yi-Jen Su ； Wei-Lin Hsu

《電腦學刊》 29卷3期 (2018/06) Pp. 165-178

https://doi.org/10.3966/199115992018062903015

摘要

Identifying all cohesion subgroups in a complex network is a critical issue in social network analysis. Once new trends coming from new actors’ interactions, a community detection method has to adopt an effective mechanism to adjust to structural changes in community composition. This research proposes a novel two-phase distributed method for dynamic overlapping community discovery on the MapReduce framework to improve performance. The first phase implements a static overlapping community detection. First, all neighbors of each node are collected from the complex network, and the TTT algorithm is applied to enumerate all maximal cliques. Following that, all adjacent maximal cliques are merged to complete the overlapping detection operation. In the second phase, the proposed dynamic overlapping community detection method is applied on influence area to adjust the struct of detected community structure. This approach applies MapReduce to adjust detected community's structure in order to avoid redundant analysis and enhance efficiency. The experiment's data are derived from YouTube users' interaction. The static overlapping community detection consists of six groups ranging from 50,000 to 300,000 nodes. The data for the dynamic overlapping community discovery consists of five groups ranging from 2,000 to 10,000 nodes, which are in turn dynamically added to the static overlapping communities to generate the final clustering results.

關鍵字

community discovery ； MapReduce ； social network analysis