利用社群網路中的互動資訊進行社群探勘

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：18.221.129.145

姓名

莊清皓(Ching-hao Chuang) 查詢紙本館藏

畢業系所

資訊管理學系

論文名稱

利用社群網路中的互動資訊進行社群探勘
(Community Detection - Based on Social Interactions in Social Network)

相關論文

★ 零售業商業智慧之探討	★ 有線電話通話異常偵測系統之建置
★ 資料探勘技術運用於在學成績與學測成果分析 -以高職餐飲管理科為例	★ 利用資料採礦技術提昇財富管理效益 -以個案銀行為主
★ 晶圓製造良率模式之評比與分析－以國內某DRAM廠為例	★ 商業智慧分析運用於學生成績之研究
★ 運用資料探勘技術建構國小高年級學生學業成就之預測模式	★ 應用資料探勘技術建立機車貸款風險評估模式之研究－以A公司為例
★ 績效指標評估研究應用於提升研發設計品質保證	★ 基於文字履歷及人格特質應用機械學習改善錄用品質
★ 以關係基因演算法為基礎之一般性架構解決包含限制處理之集合切割問題	★ 關聯式資料庫之廣義知識探勘
★ 考量屬性值取得延遲的決策樹建構	★ 從序列資料中找尋偏好圖的方法 - 應用於群體排名問題
★ 利用分割式分群演算法找共識群解群體決策問題	★ 以新奇的方法有序共識群應用於群體決策問題

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

近年來有許多各種真實世界中的網路(networks)已逐漸成為資料探勘的對象，如網際網路(worldwide web)、社群網路(social network)、引用網路(citation network)、生物網路(biological network)等，而本論文著重於目前高度使用的社群網路中進行社群探勘(community detection)。社群探勘為社群網路分析(social network analysis)中相當熱門的研究議題，希望透過對整體社群網路結構的分析，將整個網路分成多個子群體，也稱為社群(community)。
在目前大部分的社群探勘演算法中，大多為以網路結構為基礎的方法，意即從網路中或圖形中，以結構觀點來辨認次群體，找出有緊密連結的次團體如cliques, n-cliques, n-clans, n-plexes。而此類方法通常假設整個網路結構的資訊是已知的，也就是說所有在社群間的關係都清楚已知。除此之外，大部分的社群探勘演算法並不會區分不同型態的關係，而將所有關係看成單一種關係類型。若以在Facebook的情況為例，使用者可以與任何認識的人成為朋友。但在現實世界中，我們同時擁有多種身分關係是相當常見的。因此如何將Facebook上的所有朋友關係區分出不同的社群是本研究的主要研究議題。我們希望在不完整的社群網路資訊下，能夠利用社群網路上的社交互動資訊來進行社群探勘以彌補現有方法的缺陷。我們試著利用關聯規則探勘的概念來找出頻繁互動的集合，藉以作為初始的社群。接著找出最相近的兩個社群進行合併，直到社群數目達到所設定的數量為止。
在本研究的實驗中，我們從Facebook中擷取10個使用者的分享文章及個人資訊，分別做為10個實驗資料集。我們採用了Community purity與Cluster purity作為評量我們的方法所找出的社群結果之評量指標，實驗結果顯示出我們所探勘出的社群分類與使用者先行所分類的結果有高度的相關性。

摘要(英)

There has been much recent research about identifying communities in networks. Based on the online social network, which is getting more and more popular recently, we explore the community detection problem, i.e., how to identify the hidden sub-groups in the heterogeneous social network.
Traditional research on community detection usually assumed that the structural information of the network is fully known, which is not feasible for many practical networks. Moreover, most previous algorithms for community detection did not differentiate multiple relations existing among objects or persons in a real world. In Facebook, two persons can be either friend or not friend. But in reality a friend relation may come from different reasons and belong to different social groups. Thus, how to differentiate different relations among users on Facebook is a key research issue in our work. In this paper, we propose a new approach utilizing the social interaction data, rather than structural information of the network, to address the community detection problem in Facebook. Specifically, we develop a method to find the multiple social groups of a Facebook user from his/her past interaction data with friends. The advantages of our approach include: i) it does not depend on the structural information, ii) it can differentiate different relations existing among friends, iii) it allows a friend belonging to multiple communities at the same time. In the experiment, we retrieve 10 Facebook user’s data as our datasets and evaluate the performance of each dataset. The results show that our method can identify the hidden social groups of users successfully from the interaction data in Facebook. Experimental results verify the feasibility and effectiveness of our approach.

關鍵字(中)

★ 社群網路探勘
★ 資料探勘
★ 社群探勘

關鍵字(英)

★ Data mining
★ Social network mining
★ Community detection

論文目次

Abstract i
摘要 ii
誌謝 iii
Contents iv
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 RELATED WORKS 4
2.1 Cohesive Sub-structure 4
2.2 Hierarchical Clustering 5
CHAPTER 3 RESEARCH DESIGN 9
3.1 Interaction Transaction 9
3.2 Problem Definition 9
CHAPTER 4 ALGORITHM 18
CHAPTER 5 EXPERIMENTS 26
5.1 Experiment Design 26
5.2 Parameter Analysis 30
5.3 Final Test 37
5.4 Visualization of community detection 39
CHAPTER 6 CONCLUSIONS AND FUTURE WORKS 43
6.1 Conclusions 43
6.2 Future Works 44
APPENDIX 46
Detailed Figures of Datasets 46
1. Dataset 1 46
2. Dataset 2 48
3. Dataset 3 51
4. Dataset 4 53
5. Dataset 5 56
6. Dataset 6 59
7. Dataset 7 62
8. Dataset 8 64
9. Dataset 9 66
10. Dataset 10 68
REFERENCES 70

參考文獻

[1]. Albert, R., H. Jeong, and A.-L. Barabasi, Diameter of the world-wide web. Nature, 401: p. 130-131, 1999.
[2]. Wasserman, S. and K. Faust, Social Network Analysis, Cambridge: Cambridge University Press, 1994.
[3]. Li, X.-L., et al., Searching for Rising Stars in Bibliography Networks, in DASFAA, 2009.
[4]. Palla, G., et al., Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435: p. 814-818, 2005.
[5]. Li, X.-L., et al., Interaction Graph Mining for Protein Complexes Using Local Clique Merging. Genome Informatics, 16(2), 2005.
[6]. Li, X.-L., C.-S. Foo, and S.-K. Ng, Discovering Protein Complexes in Dense Reliable Neighborhoods of Protein Interaction Networks, in CSB. 2007.
[7]. Steinhaeuser, K. and N. Chawla, A Network-Based Approach to Understanding and Predicting Diseases. Springer Verlag, 2009.
[8]. Wu, M., et al., A Core-Attachment based Method to Detect Protein Complexes in PPI Networks. BMC Bioinformatics, 10(169), 2009.
[9]. Li, X.-L., et al., Computational approaches for detecting protein complexes from protein interaction networks: a survey. BMC Genomics, 11(Suppl 1: S3), 2010.
[10]. Redner, S., How popular is your paper? An Empirical Study of the Citation Distribution. Eur. Phys. J., B (4): p. 131-138, 1998.
[11]. Nisheeth, S., M. Anirban, and R. Rastogi, Mining (Social) Network Graphs to Detect Random Link Attacks in ICDE, 2008.
[12]. J. Scott. Social Network Analysis: A Handbook. Sage Publications, London, 2002.
[13]. C. Bron and J. Kerbosch. Finding all cliques of an undirected graph. Communications of the ACM, 16:575-577, 1973.
[14]. N. Du, B. Wu, and B. Wang. A parallel algorithm for enumerating all maximal cliques in complex networks. The 6th ICDM2006 Mining Complex Data Workshop, pages 320-324. IEEE CS, December 2006.
[15]. B. Wu and X. Pei. A parallel algorithm for enumerating all the maximal k-plexes. In PAKDD07 Workshops, May 2007.
[16]. J. Abello, M. Resende, and S. Sudarsky. Massive quasi-clique detection. In 5th Latin American Symposium on Theoretical Informatics, pages 598-612, 2002.
[17]. J. Pei, D. Jiang, and A. Zhang. On mining cross-graph quasi-cliques. In The 12th ACM SIGKDD, pages 228-237, 2006.
[18]. Z. Zeng, J. Wang, and G. Karypis. Coherent closed quasi-clique discovery from large dense graph databases. In The 12th ACM SIGKDD, pages 797-802, 2006.
[19]. J. Han and M. Kamber. Data Mining: Concepts and Techniques, 2nd ed. Morgan Kaufmann Publishers, 2006.
[20]. M. Girvan and M. Newman. Community structure in social and biological networks. PNAS, 99(12):7821-7826, June 2002.
[21]. Donetti L and Munoz MA Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics: Theory and Experiment, P10012, 2004
[22]. M. Girvan and M. Newman. Finding and evaluating community structure in networks. Physical Review E, 69(026113), 2004.
[23]. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. PNAS, 101(9):2658-2663, March 2004.
[24]. A. Clauset, M. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70(066111), 2004.
[25]. P. Pons and M. Latapy. Computing communities in large networks using random walks. In ISCIS2005, pages 284-293, 2005.
[26]. C. G. Akcora, B. Carminati, and E. Ferrari: Network and profile based measures for user similarities on social networks. IRI: 292-298, 2011.
[27]. K. Jones. A statistical interpretation of term speciﬁcity and its application in retrieval. Journal of documentation, 28(1):11–21, 1993
[28]. M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27:415–444, 2001.
[29]. The Open Graph Viz Platform https://gephi.org/

指導教授

陳彥良(Yen-Liang Chen)

審核日期

2012-6-29

推文