以馬可夫鏈方法進行相對重要性分析與社群結構偵測

A Markov Chain Approach for Relative Centrality and Community Detection

吳牧寰

指導教授 ： 張正尚

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

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

摘要

我們在最近的研究中發展出一套針對網路進行結構分析的機率架構。在該架構中我們從具有對稱性質的二元機率分布(bivariate distribution)出發，以此機率分布對網路進行取樣，並且定義諸多概念，例如:相對重要性、重要性、社群強度以及模塊性(Modularity)。基於這些概念，我們進而提出一些進行區域社群偵測的演算法。
而該機率架構有一個已知的缺陷，即是該二元機率分布必須具有對稱性質，也因此限制了能套用此架構的網路必須為無方向性。本論文之其中一目的即為延伸此架構的限制，使非對稱性的二元機率分布也能被允許。對了達到上述的目的，我們將馬可夫鏈的觀念引進至該架構，並且證明了相對重要性、重要性、社群強度以及模塊性的概念也能一併被延伸。然而在原本的架構中具有的某些性質也因此相對的弱化，特別是相互性質。也因此我們必須要擴增鄰近集合的定義，進一步修改原先提出的演算法。另外基於馬可夫鏈的狀態合成性質，我們也發展了一套進行狀態簡化並保留模塊性質的方法，該方法讓我們能夠不斷減少原先馬可夫鏈狀態集合的大小，但卻和原先的馬可夫鏈具有相同的模塊性。在使用該方法之後，我們即可以在有方向性的大型網路上進行快速社群偵測。
在此論文中，我們也提出了一些將有方向性網路對應到馬可夫鏈上的方法，包括了隨機漫步(Random Walk)、佩奇排名(PageRank)以及擴散方法。而這些不同的對應方法在不同面向的考量下都有其各自的優點，尤其是擴散方法能讓我們在不同的時間規模中偵測出對應的社群結構，我們並且在附錄中證明了擴散方法底下的社群強度具有單調下降的性質。

關鍵字

網路科學 ； 社群偵測 ； 馬可夫鏈 ； 相對重要性 ； 演算法

並列摘要

In our recent work, we developed a probabilistic framework for structural analysis of
networks. In that framework, we start from sampling a network by a symmetric bivariate
distribution and use that bivariate distribution to dene various concepts, including relative
centrality, centrality, community strength, and modularity. Based on these concepts,
we then proposed a class of local community detection algorithms. One drawback for
this framework is that the bivariate distribution has to be symmetric and that limits its
applicability to undirected networks. The main objective of this paper is to extend such
a framework to the setting where asymmetric bivariate distribution can be allowed. Our
approach for the extension is to introduce Markov chains into the framework. We show
that relative centrality, centrality, community strength and modularity can be extended
in a similar manner. However, various properties, in particular the reciprocity property,
are much weaker than before. As such, the local community detection algorithms need
to be further modied by taking a larger neighboring set into account. By using the
state aggregation property of Markov chains, we also develop a method for modularity
preserving state reduction of a Markov chain. This method allows us to reduce the size of
the states of a Markov chain while preserving its modularity. With such a state reduction
method, we are then able to perform fast community detection for directed networks with
a large number of nodes.
In this paper, we also propose several methods of mapping directed networks to Markov
chains, including random walks, PageRank and diusion. All these mappings have
their own merits in structural analysis of networks. In particular, the diusion approach
allows us to detect communities with respect to various time scales and we show that the
community strength of a community under diusion is decreasing in time.

並列關鍵字

network science ； community detection ； Markov chain ； relative centrality ； algorithm

參考文獻

[1] Cheng-Shang Chang, Chih-Jung Chang, Duan-Shin Lee, andWanjiun Liao. Relative

centrality and local community detection. Preprint.

[2] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web

search engine. Computer networks and ISDN systems, 30(1):107{117, 1998.

[3] Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank