對動態社群網路的階層式分群與視覺化設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：18.119.19.16

姓名

吳帝華(Di-hua Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

對動態社群網路的階層式分群與視覺化設計
(The Design of Hierarchical Clustering and Visualization Methodology for the Dynamic Social Network)

相關論文

★ 應用自組織映射圖網路及倒傳遞網路於探勘通信資料庫之潛在用戶	★ 基於社群網路特徵之企業電子郵件分類
★ 行動網路用戶時序行為分析	★ 社群網路中多階層影響力傳播探勘之研究
★ 以點對點技術為基礎之整合性資訊管理及分析系統	★ 在分散式雲端平台上對不同巨量天文應用之資料區域性適用策略研究
★ 應用資料倉儲技術探索點對點網路環境知識之研究	★ 從交易資料庫中以自我推導方式探勘具有多層次FP-tree
★ 建構儲存體容量被動遷徙政策於生命週期管理系統之研究	★ 應用服務探勘於發現複合服務之研究
★ 利用權重字尾樹中頻繁事件序改善入侵偵測系統	★ 有效率的處理在資料倉儲上連續的聚合查詢
★ 入侵偵測系統：使用以函數為基礎的系統呼叫序列	★ 有效率的在資料方體上進行多維度及多層次的關聯規則探勘
★ 在網路學習上的社群關聯及權重之課程建議	★ 在社群網路服務中找出不活躍的使用者

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在社群網路分析的領域裡，將社群網路中個體的互動關係進行分群一直是個重要的議題。以往的研究中，大部分的分群方法都是在靜態或是涵蓋社群網路整體時間的概念下，而實際的社群網路是會經過時間而演化的，社群網路中個體的互動有可能在某段時間發生變化，進而影響社群網路中的社群結構，對於這樣演化的社群網路進行分群的話，效率便成為一個重要的問題。
本研究共分兩個部分，第一部分為設計一個遞增分群(incremental clustering)方法，來解決分群效率的問題。將社群網路從傳統的快照圖模型(snapshot model)轉換成改變流模型(change stream model)，並結合平衡式階層社群建立(balanced hierarchy construction)演算法，來提供一個遞增版本的平衡式階層社群建立演算法。在第二部分，對應於社群網路演化中分群所產生的結果，提供一個視覺化的設計，連結長條圖，這個視覺化方法是以社群為視點，來了解在暫時的時間下，不同階層時的社群關係。
在實驗中，本研究透過分析Enron電子郵件，顯示出相對於原始的靜態分群方法，本研究提供的方法明顯的讓分群的效率有所改進。對於演化過程中暫時的社群結構，透過視覺化方法也可實際觀察出正確的分群結果，而利用比對於不同時間的結果，也能觀察出社群的變化。

摘要(英)

Detect the communities in social network by interactions of entities which is an important issue in social network analysis. Mostly, clustering algorithms are under static point or entire time of social networks concept. Real social networks usually evolve continuously with the passage of time. Interactions of entities might change at some point in time and make the community structures also change. Because of this situation, the problem of efficiently clustering appear.
The research is composed of two parts: first of all, this paper present a design of incremental clustering to address the problem of efficiency. Transform the social network from traditional snapshot graph model to change stream model, and combine with balanced community hierarchy construction. Second, the design of visualization, connective bar chart, to satisfy the results created in dynamic social networks. The visualization is based on the view of communities and can understand the temporal view of the relationship among communities in different level.
Experiment with the analysis of Enron e-mail, the results represent that our method can improve the efficiency apparently compare with the static method. The community structures also present a correct results and the difference between two periods by our design of visualization.

關鍵字(中)

★ 社群網路分析
★ 動態社群網路
★ 遞增式分群
★ 變化流模型

關鍵字(英)

★ Social network analysis
★ Dynamic social network
★ Incremental clustering
★ Change stream model

論文目次

摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 vi
一、緒論 1
1-1 研究背景 1
1-2 研究動機與目的 2
1-3 論文架構 4
二、文獻探討 5
三、背景與系統設計 8
3-1 改變流模型 8
3-2 平衡階層建立演算法 8
3-3 資料處理階段 10
3-4 模型萃取階段 11
3-5 系統分析階段 13
四、研究方法 14
4-1 遞增式平衡階層分群 14
4-2 邊刪除更新 16
4-3 邊加入更新 20
4-4 差異性 21
五、系統展示 24
5-1 資料來源 24
5-2 連結長條圖 24
5-3 系統實作 27
5-3-1 介面配置 27
5-3-2 操作與設定控制 28
5-4 結果討論 30
5-4-1 社群與連結為獨立呈現 30
5-4-2 觀察社群組成的改變 31
5-4-3 觀察社群之間的關係強度 32
5-4-4 了解每個階層的社群成員 34
六、實驗 35
6-1 實驗設定 35
6-2 實驗結果 35
七、結論 40
參考文獻 41

參考文獻

[1] Achtert E., Böhm C., Kröger P., DeLi-Clu: boosting robustness, completeness, usability, and efficiency of hierarchical clustering by a closest pair ranking. PAKDD′06 Proceedings of the 10th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining, 2006, 119-128
[2] Ankerst M., Breunig M. M., Kriegel H. P., Sander J., OPTICS: ordering points to identify the clustering structure. SIGMOD ′99 Proceedings of the 1999 ACM SIGMOD international conference on Management of data, 1999, 49-60
[3] Arthur D., Vassilvitskii S., k-means++: the advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, 1027-1035
[4] Bagheri A., Razzazi M., Drawing Free Trees Inside Simple Polygons Using Polygon Skeleton. COMPUTING AND INFORMATICS 23, 2004, 239-254
[5] Chakrabarti D., Kumar R., Tomkins A., Evolutionary clustering. Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, 554-560
[6] Chi Y., Song X., Zhou D., Hino K., Tseng B. L., Evolutionary spectral clustering by incorporating temporal smoothness. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 153-162
[7] Defays D., An efficient algorithm for a complete link method. The Computer Journal 20, 1977, 364-366
[8] Dempster A. P., Laird N. M., Rubin D. B., Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological) 39, 1977, 1-38
[9] Diesner J., Frantz T. L., Carley K. M., Communication Networks from the Enron Email Corpus "It′s Always About the People. Enron is no Different". Computational & Mathematical Organization Theory 11, 2005, 201-228
[10] Duan D., Li Y., Li R., Lu Z., Incremental K-clique clustering in dynamic social networks. Artificial Intelligence Review 38, 2012, 129-147
[11] Dunne C., Shneiderman B., Motif Simplification: Improving Network Visualization Readability with Fan and Parallel Glyphs. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 2013, 3247-3256
[12] Ester M., Kriegel H. P., Sander J., Xu X., A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Second International Conference on Knowledge Discovery and Data Mining, 1996, 226-231
[13] Girvan M., Newman M. E. J. , Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the United States of America 99, 2002, 7821-7826
[14] Goble G., The History of Social Networking. http://www.digitaltrends.com/features/the-history-of-social-networking/#!Q1FqY
[15] Görke R., Hartmann T., Wagner D., Dynamic Graph Clustering Using Minimum-Cut Trees. Algorithms and Data Structures 5664, 2009, 339-350
[16] Hamerly G., Elkan C., Alternatives to the k-means algorithm that find better clusterings. International Conference on Information and Knowledge Management, 2003, 578
[17] Herman I., Merlancon G., Marchall M. S., Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics 6, 2000, 24-43
[18] http://www.classmates.com/
[19] http://www.edrm.net/
[20] https://www.cs.cmu.edu/~enron/
[21] Jia Y., Garland M., Hart J. C., Social Network Clustering and Visualization using Hierarchical Edge Bundles. Computer Graphics Forum 30, 2011, 2314-2327
[22] Jia Y., Hart J. C., Drawing Trees: How Many Circles to Use? 2009
[23] Murtagh F., Complexities of hierarchic clustering algorithms: state of the art, Computational Statistics Quarterly 1, 1984, 101-113
[24] Ning H., Xu W., Chi Y., Gong Y., Huang T. S., Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition 43, 2010, 113-127
[25] Palla G., Derényi I., Farkas I., Vicsek T., Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 2005, 814-818
[26] Park H. S., Jun C. H., A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications 36, 2009, 3336-3341
[27] Pérez-Suárez A., Martínez-Trinidad J. F., Carrasco-Ochoa J. A., Medina-Pagola J. E., An algorithm based on density and compactness for dynamic overlapping clustering. Pattern Recognition 46, 2013, 3040-3055
[28] Sibson R., SLINK: An optimally efficient algorithm for the single-link cluster method. The Computer Journal 16, 1973, 30-34
[29] Social Media Update 2013, http://www.pewinternet.org/2013/12/30/social-media-update-2013/
[30] Sun J., Faloutsos C., Papadimitriou S., Yu P. S., GraphScope: parameter-free mining of large time-evolving graphs. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 687-696
[31] Tantipathananandh C., Berger-Wolf T., Kempe D., A framework for community identification in dynamic social networks. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 717-726

指導教授

蔡孟峰(Meng-Feng Tsai)

審核日期

2014-8-26

推文