異質性社群網路探勘：中心度、分群、資訊摘要

Mining Heterogeneous Social Networks: Centrality, Clustering, and Abstraction

李政德(Cheng-Te Li)

指導教授 ： 林守德

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00207

摘要

社群網路是一種能夠描述個體彼此關係之資料結構，至目前相關研究人員在具有單一個體類型與單一關係類型之同質性網路，已成功提出許多網路分析之方法。然而，真實世界之複雜網路通常為異質性，亦即存在多重類型之個體與關係。本論文整合高階關係類型資訊，提出一種非監督式、以tensor為基礎之方法與模型，來捕捉異質性網路中節點之語意於一種signature profile之特徵空間。基於該模型，本論文解決三個異質性網路探勘之議題。首先，我們提出貢獻度、多樣性程度與相似度之三種異質性中心度指標，來衡量節點之重要性；接著，我們考慮節點於網路中扮演之角色來進行分群；最後，為簡化社群網路探查與視覺化之複雜度，我們萃取關於使用者指定節點之三種最具代表性的資訊，來進行以個體為中心之網路摘要。本論文使用一真實之電影網路與一合成之犯罪網路來進行實驗評估，對於異質性中心度量測與網路角色分群，我們展示探勘之結果及其物理意義，對於以個體為中心之資訊摘要，我們用於人為主觀之罪犯偵測，實驗結果顯示我們的方法能提供高準確、高效率、高信心水準之罪犯偵測。

關鍵字

社群網路 ； 中心度 ； 分群 ； 資訊摘要 ； 異質性網路

並列摘要

Social network is a powerful data structure allowing the depiction of relationship information between entities. Recent researchers have proposed many successful methods on analyzing homogeneous social networks, assuming only a single type of node and relation. Nevertheless, real-world complex networks are usually heterogeneous, which presumes a network can be composed of different types of nodes and relations.
In this thesis, we propose an unsupervised tensor-based mechanism, considering higher-order relational information, to model the complex semantics of nodes. The signature profiles are derived as a vector-based representation to enable further mining algorithms. Moreover, based on this model, we present solutions to tackle three critical issues in heterogeneous networks. First, we identify different aspects of central individuals through three proposed measures, including contribution-based, diversity-based, and similarity-based centrality. Second, we propose a role-based clustering method to identify nodes playing similar roles in the network. Third, to facilitate further explorations and visualization in a complex network data, we devise the egocentric information abstraction and address it by proposing three abstraction criteria to distill representative and significant information with respect to any given node. In the end, the evaluations are conducted on a real-world movie dataset, and an artificial crime dataset. We demonstrate the proposed centralities and role-based clustering can indeed find some meaningful results. And the effectiveness of the egocentric abstraction is shown by providing more accurate, efficient, and confidential crime detection for human subjects.

並列關鍵字

Social Network ； Centrality ； Clustering ； Information Abstraction ； Heterogeneous Network

參考文獻

[1] P. Appan, H. Sundaram and B. L. Tseng. Summarization and Visualization of Communication Patterns in a Large-Scale Social Network. In Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’06), 371-379, 2006.

[2] P. Bonacich. Factoring and Weighting Approach to Status Scores and Clique Identification. Journal of Mathematical Sociology, 2(2), 113-120, 1972.

[3] R. Breiger, S. Boorman, and P. Arabie. An Algorithm for Clustering Relational Data with Application to Social Network Analysis and Comparsion with Multidimensional Scaling. Journal of Mathematical Psychology, 12: 328-383, 1975.

[5] D. Chakrabarti and C. Faloutsos. Graph Mining: Laws, Generators, and Algorithms. ACM Computing Survey, 38(1), 2006.

[6] J. Chen, O. R. Zaiane, and R. Goebel. Detecting Communities in Social Networks Using Max-Min Modularity. In Proceedings of SIAM International Conference on Data Mining (SDM’09), 978-989, 2009.