臺灣博碩士論文加值系統

網路架構可以被轉換成以點、線組成的圖形，而網路分群的問題就像是圖形劃分的問題。在這篇論文中，我們一開始先複習紐曼提出的模組化數值及它的機率定義，模組化數值可以度量分群結果的好壞也是這篇論文之後會一直使用到的工具；另外還複習三個廣泛被使用的多層解析度網路分群演算法，多層解析度分群演算法可以藉由控制一個參數大小來調整分群的解析度，也就是粗略地分群或是分得比較精細。
接著我們提出一個統合性的理論來統合上述三個演算法，也就是使用二元分布來從新定義輸入演算法的網路圖形，它的關鍵想法是考慮隨機選取任一路徑的機率分布而不是隨機選取任一線段的機率分布。我們只需要選擇適合的二元分布版本及特定的二元分布參數來定義新的網路圖形且把它輸入模組化數值並驗證上述那三個廣泛被使用的多層解析度網路分群演算法都是二元分布的特例，此外還提出了兩種相似性演算法來和上述三個多層解析度分群演算法做比較。
關於二元分布，我們提出了一個直覺，隨機選取任一路徑的機率分布裡如果長路徑的比重越高，分群的結果就會越粗略，也就是分的群大小越大，相反的，如果短路徑的比重越高，分群的結果就會越精細；我們使用已知群組架構之隨機圖形的電腦模擬來驗證我們的直覺。

Contents
List of Figures
1 Introduction
2 Preliminaries
2.1 Notations
2.2 Modularity
2.3 A probabilistic definition of community
3 Review of three multi-resolution functions
3.1 Multi-resolution function with parameter γ
3.2 Multi-resolution function with parameter r
3.3 Multi-resolution function with parameter t
4 An unied theory for multi-resolution functions
4.1 A random selection of a path on a graph
4.1.1 Multi-resolution function with parameter r
4.1.2 Truncated Katz similarity
4.2 A random walk on a graph
4.2.1 Multi-resolution function with parameter γ
4.2.2 Multi-resolution function with parameter t
4.2.3 Truncated PageRank similarity
5 Simulation results
5.1 Random graphs with known community structure
5.2 Karate club
5.3 Synthetic network for resolution limit
6 Conclusion

[1] Cheng-Shang Chang, Chin-Yi Hsu, Jay Cheng, and Duan-Shin Lee, “A general
probabilistic framework for detecting community structure in networks,” IEEE INFOCOM
2011.
[2] Fortunato, “Community detection in graphs,” Physics Reports, 2010.
[3] M. A. Porter, J.-P. Onnela, and P. J. Mucha “Communities in Networks,” Notices
of the American Mathematical Society, vol. 56, no. 9, pp. 1082-1097, 2009.
[4] J. Reichardt and S. Bornholdt, “Statistical mechansics of community detection,”
Physical Review E, vol. 74, 016110, 2006.
[5] A. Arenas, A. Fern´andez and S. G´omez, “Analysis of the structure of complex networks
at different resolution levels,” New J. Phys., vol. 10, 053039, 2008.
[6] R. Lambiotte, J.-C. Delvenne and M. Barahona, “Laplacian dynamics and multiscale
modular structure in networks,” arXiv :0812.1770, 2008.
[7] Lambiotte R., “Multi-scale modularity in complex networks,” 2010 Proceedings of
the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc
and Wireless Networks(WiOpt), 546-553, 2010.
[8] J.-C. Delvenne, S. Yaliraki and M. Barahona, “Stability of graph communities across
time scales,” P.N.A.S., 107(29) :12755-12760, 2010.
[9] S. Fortunato and M. Barth´elemy, “Resolution limit in community detection,” Proc.
Natl. Acad. Sci. U.S.A., vol. 104, pp.36-41, 2007.
[10] A. Clauset, M. E. J. Newman, C. Moore, ”Finding community structure in very
large networks,” Physical Review E, 2004.
[11] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,”
PHYSICAL REVIEW E, vol. 69, 066133, 2004.
[12] M. E. J. Newman and M. Girvan, ”Finding and evaluating community structure in
networks,” Physical Review E, vol. 69, 026113, 2004.
[13] Muff S, Rao F, Caflisch A “Local modularity measure for network clusterizations,”
Phys Rev E 72:056107, 2005.
[14] Hristo Djidjev, “A scalable multilevel algorithm for graph clustering and community
structure detection,” Workshop on Algorithms and Models for the Web Graph,
Lecture Notes in Computer Science, pages LA-UR-06-6261, 2006
[15] P. Erd¨os and A. R´enyi, “On random graphs,” Publicationes Mathematicae Debrencen
6, 290, 1959.
[16] W. W. Zachary, J. Anthropol, Res. 33, 452, 1977.