相對重要性與區域社群偵測

Relative Centrality and Local Community Detection

張芝榮

指導教授 ： 張正尚

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2013年)

https://doi.org/10.6843/NTHU.2013.00731

摘要

在論文中，我們對於社群定義和社群強度評估發展了一套完整架構，不僅提供深入的物理現象觀察，對各種網路分析方法也能有統一的解釋。並針對區域社群偵測問題提出一個能保證偵測結果之社群強度的演算法。
在我們的架構之中，其中一個關鍵的創新就是在網路結構分析中提出了一個新穎的概念「相對重要性」。基於相對重要性，我們定義了社群強度的量測方式。而社群則定義為一組社群強度不為負值的節點集合。基於社群的定義，我們也證明一些對於社群的數學等價描述，並能解釋它們的社會意義。我們也展示社群強度和導度(conductance)的相關性，並定義一個網路的模塊性(modularity)為其子圖社群強度的加權平均。在這樣的定義下，不僅概括了原來模塊性的定義，也能解釋穩定性(stability)為我們的一種特殊情形。
而針對區域社群問題，我們發展了一套凝聚型的演算法，可以保證偵測結果之社群強度。該演算法有兩個良好性質：只需探索相鄰集合(neighboring set)中的節點資訊，並能藉由遞迴公式快速更新相對重要性。因此，我們的演算法的不僅複雜度與參考文獻[4]中的演算法相近，更能考慮群聚係數(clustering coefficient)的影響。最後，從我們的實驗結果可以看出，對於社群強度較強的節點集合，我們的演算法的偵測結果可以達到100%的查準率(precision)和查全率(recall)。

關鍵字

網路科學 ； 區域社群偵測 ； 重要性 ； 模塊性 ； 分群演算法

並列摘要

無資料

並列關鍵字

network science ； local community detection ； centrality ； modularity ； clustering algorithms

參考文獻

[46] Xuan-Chao Huang, Jay Cheng, Hsin-Hung Chou, Chih-Heng Cheng, and Hsien-

[1] Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004.

[2] Renaud Lambiotte. Multi-scale modularity in complex networks. In Modeling and

[4] Aaron Clauset. Finding local community structure in networks. Physical review E,

72(2):026132, 2005.