基於連結性分析結果所設計的分散式社群偵測方法

A Scalable Distributed Method for Community Detection based on Connectivity Evaluation

雷政霖(Cheng-Lin Lei)

指導教授 ： 李新林

國立中正大學/工學院/資訊工程學系/碩士(2016年)

摘要

模組最大化(Modularity Maximization)被廣泛用於社群偵測問題上，基於模組最大化的演算法在小型網路上有很高的精確度。然而在多數的電腦上針對大型網路進行會有效能瓶頸。在本篇論文裡，我們提出一個能在分散式系統平行運算的演算法。並提出一個能平行化的評估函數取代模組最大化公式。在實驗中，我們建造了一個分散式系統，在此分散式系統中，我們實作了一個基於Redis的緩存(Cache)機制，並以Apache Spark作為分散式運算平台。結果顯示我們方法在一千點以上的網路可透過新增機器數提升速度(Scalability)，並在具有一萬個節點的大型網路上能比現有的單機方法更有效率。

關鍵字

分散式系統 ； 非重疊之社群結構 ； 社群偵測 ； 資料探勘 ； 分散式運算

並列摘要

For community detection, modularity is a widely-used objective function. A partition result which has high modularity score represents a partitioning that it may be similar to real community structures hidden in the network. Many algorithms based on modularity maximization are proposed. The performance of these algorithms usually have high accuracy on small networks. However, they are not suitable to be applied on large-scale networks which have more than ten thousand nodes. In order to solve the community detection problem on a large-scale network in an efficient way, we propose a method called Scalable Distributed Partition Method (SDPM). A new value function called Connectivity Evaluation Method (CEM) is proposed and used in the SDPM. The SDPM partitions a large-scale network in parallel in a cluster. A cluster which is built by Apache Spark and NoSQL database Redis are implemented to evaluate the performance of our proposed method. In the experiments, our method is more efficient on large-scale networks than a community detection algorithm based on Modularity called Vector Partition at Polar Coordinate (VPPC), and our algorithm is scalable that it could gain more computation power from increasing the number of used machines without modifying any codes.

並列關鍵字

distributed computing ； distributed system ； non-overlapping communities ； community detection ； data mining

參考文獻

[1] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E, vol. 74, p. 036104, Sep 2006.

[3] S. Fortunato and M. Barth‘elemy, “Resolution limit in community detection,” Proceedings of the National Academy of Sciences, vol. 104, no. 1, pp. 36-41, Jan 2007.

[4] Mingming Chen, Kuzmin, K., and Szymanski, B.K., “Community Detection via Maximization of Modularity and Its Variants,” IEEE Transactions on Computational Social Systems, vol. 1, no. 1, pp. 46-65, Mar 2014.

[5] Mingming Chen, Tommy Nguyen, and Boleslaw K. Szymanski, “A New Metric for Quality of Network Community Structure,” ASE Human Journal, vol. 2, no. 4, pp. 226-240, 2013.

[7] W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of Anthropological Research, vol. 33, pp. 452-473, 1977.