A Novel Community Detection Algorithm Based on E_FEC

10.3966/199115992017102805007

Lidong Wang；Yun Zhang；Yin Zhang；Huixi Zhang

community detection ； E_FEC algorithm ； FEC algorithm ； random walk

電腦學刊

28卷5期（2017 / 10 / 01）

70 - 81

英文

FEC adopts an agent-based heuristic that makes the algorithm efficient and is presented with two phases that are Finding Community (FC) and Extraction Community (EC). Although designed with linear running time, original FEC can not obtain ideal results on the graph whose community structure is not well defined. This paper extend FEC as E_FEC to seek a good trade-off between effectiveness and efficiency. In FC phase, we calculate the accumulative transition probability to find the existence of communities, and propose an automatic selection algorithm for the sink node. In EC phase, we present another simpler cut criterion based on Average cut (Acut) which costs less running-time in EC phase. The performance of E_FEC is rigorously validated through comparisons with other representative methods against both synthetic and real-world networks with different scales.