【摘要】：隨著信息技術的飛速發(fā)展,Twitter、Facebook、新浪微博、微信等各類在線社交平臺逐漸改變人們的生活和工作方式。在這些平臺上,每天產生大量、繁雜的網絡數(shù)據(jù),包括節(jié)點鏈接關系數(shù)據(jù)和內容屬性數(shù)據(jù)。鏈接關系數(shù)據(jù)隱含網絡統(tǒng)計特性、潛在結構和交互規(guī)律,內容屬性數(shù)據(jù)包含豐富的數(shù)字圖像、文本和音頻等描述節(jié)點特征屬性的內容信息。對這些復雜的網絡數(shù)據(jù)進行挖掘和分析為機器學習、數(shù)據(jù)挖掘等領域提供了新的機遇和挑戰(zhàn)。網絡的社區(qū)發(fā)現(xiàn)是進行網絡分析的一個基本問題,這對實現(xiàn)數(shù)據(jù)的自然劃分、數(shù)據(jù)壓縮、可視化分析、以及內容推薦等具有重要的科學意義和應用價值。該問題提出以來,各種社區(qū)發(fā)現(xiàn)方法和技術應運而生,其中,K-means聚類算法由于其思想簡單、易于實現(xiàn)、對大規(guī)模數(shù)據(jù)的處理具有高效性和可伸縮性等,在網絡數(shù)據(jù)的節(jié)點劃分中得到廣泛應用。但該算法也存在明顯的缺陷:1)對初始點的選取十分敏感,其性能容易受初始種子節(jié)點的影響;2)要求預先指定聚類個數(shù)。因此,針對網絡型數(shù)據(jù)的特性,如何提出K-means型劃分聚類方法的初始化策略有待進一步研究。研究發(fā)現(xiàn),實際網絡通常稀疏而且存在噪聲信息,對于社區(qū)結構不清晰的網絡,如何利用網絡中輔助信息挖掘有意義的社區(qū)結構為研究者提出新的要求。本文以網絡數(shù)據(jù)為研究對象,對K-means型劃分聚類方法中的聚類個數(shù)、初始點選取、如何有效處理社區(qū)結構不清晰網絡以及將節(jié)點的屬性特征進行有效結合展開研究,并對如何考慮邊的不確定性進行探索。本文的主要研究成果包括:1)提出了一種基于節(jié)點中心度和離散度的社區(qū)發(fā)現(xiàn)方法。根據(jù)網絡數(shù)據(jù)的特性,基于網絡中節(jié)點的中心度和離散度兩個量化指標,從決策圖和綜合得分兩個角度給出確定聚類個數(shù)和初始中心選擇的策略,為基于K-means型方法進行網絡的社區(qū)發(fā)現(xiàn)提供一定的指導,人工網絡和實際網絡上的對比實驗驗證了提出方法的有效性。在該方法基礎上,提出了一種通過節(jié)點屬性的k近鄰圖(k Nearest Neighbor, kkNN)增強的社區(qū)發(fā)現(xiàn)方法,通過節(jié)點的屬性相似性對原始鏈接關系網絡進行增強,從而降低網絡稀疏性和噪聲對節(jié)點劃分的影響。實驗對比表明該方法不僅能夠處理不同節(jié)點屬性類型的網絡,而且具有較高的劃分準確率。2)提出了主動融合先驗信息的社區(qū)發(fā)現(xiàn)方法。對于社區(qū)結構不清晰的網絡,通常難以準確選取聚類個數(shù)和初始中心,而且節(jié)點容易劃分錯誤�；谥鲃訉W習,提出一種主動選擇節(jié)點和鏈接的策略。該方法是一種雙向方法,通過增強節(jié)點到所屬類的凝聚力并增大類間距離使邊界清晰化,從而提高節(jié)點劃分的準確率。而且,通過主動選擇節(jié)點,能夠自動估計社區(qū)個數(shù)并選擇初始中心。該方法能夠以少量的人工標注,顯著提高節(jié)點劃分的準確率。3)提出了一種自適應融合鏈接結構信息和節(jié)點內容屬性信息的社區(qū)發(fā)現(xiàn)方法(Adapt fusion of structural and attribute information, Adapt-SA)。該方法是一種局部加權的K-means模型,通過交替迭代,能夠自動學習每個節(jié)點在兩種異構信息的融合權重以及節(jié)點劃分的隸屬度矩陣。該方法得到的節(jié)點劃分結果,使得同類的節(jié)點不僅鏈接緊密,而且具有較高的屬性相似性。理論和實驗驗證了算法的收斂性,實驗分析了模型對信息融合權重學習的有效性。通過與其他融合節(jié)點屬性的社區(qū)發(fā)現(xiàn)方法對比,表明了Adapt-SA方法的性能。4)提出了不確定屬性網絡中的社區(qū)發(fā)現(xiàn)方法�，F(xiàn)實網絡中節(jié)點之間的邊通常具有不確定性,而且節(jié)點具有高維的屬性信息。針對這類復雜的網絡數(shù)據(jù),本章提出不確定屬性網絡的社區(qū)發(fā)現(xiàn)方法,綜合考慮邊的不確定性以及節(jié)點的屬性信息。通過邊的不確定性提取出重要的節(jié)點屬性,進一步利用重要屬性減弱邊的不確定性以挖掘有意義的社區(qū)結構。人工網絡以及實際網絡的實驗對比證明了方法的有效性,參數(shù)的實驗分析驗證了對抽樣數(shù)以及權重閾值的魯棒性。
【圖文】：

合節(jié)點鏈接關系和節(jié)點屬性的社區(qū)發(fā)現(xiàn)方法（見第五章）�？紤]網絡中鏈接關系逡逑的不確定性，對不確定網絡中融合節(jié)點屬性信息的社區(qū)發(fā)現(xiàn)方法進行初步探索逡逑（見第五章）。圖１．２給出本論文四個研宄內容的關系框架圖，其詳細介紹如下：逡逑１）基于節(jié)點中心度和離散度的社區(qū)發(fā)現(xiàn)方法逡逑Ｋ－ｍｅａｎｓ型網絡社區(qū)發(fā)現(xiàn)方法中，聚類個數(shù)和初始中心選擇是研宄的重點和逡逑難點，以往方法大多需要引入額外參數(shù)。針對這個問題，本文根據(jù)網絡數(shù)據(jù)的特逡逑性，基于網絡中節(jié)點的中心度和離散度，從決策圖和綜合得分兩個角度給出確逡逑定聚類個數(shù)的方案，為Ｋ－ｍｅａｎｓ型方法提供一種新的初始中心節(jié)點的選擇策略，逡逑并提出一種無參數(shù)調節(jié)的社區(qū)發(fā)現(xiàn)方法Ｋ－ｒａｎｋ－Ｄ�；诖耍M一步對融合節(jié)點屬逡逑性網絡的社團劃分方法進行研宄，提出基于節(jié)點的屬性增強的方法ＡＮＮ－ｅｎｈａｎｃｅ。逡逑該方法利用節(jié)點的屬性相似性對原始鏈接關系進行增強，從而降低網絡稀疏性和逡逑噪聲對節(jié)點劃分的影響。逡逑１２逡逑

殊網絡（記為特殊網絡１）由三個類組成，其中一個類是由４００個節(jié)點構成的很大逡逑的派系（全連接的團），其他兩個類都是１３個節(jié)點構成，這三個類彼此通過一條逡逑邊相連，如圖２．１邋（ａ）所示。第二個特殊網絡（記為特殊網絡２）由１００個小派系，逡逑每一個派系有５個節(jié)點，這些派系彼此通過一條邊首尾相接，從而形成一個類似逡逑環(huán)形的結構，圖２．１邋（ｂ）展示了一個由５個派系組成的例子。逡逑（二）真實數(shù)據(jù)集逡逑真實數(shù)據(jù)集可細分為只有鏈接結構的數(shù)據(jù)及融合鏈接結構和節(jié)點屬性的數(shù)逡逑據(jù)。逡逑（１）鏈接結構網絡逡逑？邐Ｚａｃｈａｒｙ’邋ｓ邋ｃｌｕｂ網絡又稱Ｋａｒａｔｅ網絡｜１３１】，是空手道俱樂部網絡，，由３４個節(jié)逡逑點組成，每個節(jié)點表示一個成員，邊表示成員之間的社交關系。由于俱樂部逡逑主管和校長發(fā)生矛盾，俱樂部成員就分成了分別以主管和校長為中心的兩個逡逑類。逡逑？邐Ｒｉｓｋ網絡［１３２］是一個具有４２個節(jié)點６個類的網絡，該網絡表示一個很流行的逡逑棋盤游戲；逡逑？邐Ｄｏｌｐｈｉｎｓ網絡【１３３］是由６２個海豚構成，連邊表示兩個海豚之間接觸頻繁，被逡逑分成２個群體。逡逑？邐Ｌｅｓｍｉｓ網絡［１３４］是根據(jù)Ｖｉｃｔｏｒ邋Ｈｕｇｏ的小說《悲慘世界》中角色是否同時出現(xiàn)逡逑而建立的
【學位授予單位】：北京交通大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP311.13

【參考文獻】

相關期刊論文 前3條

1 任曉龍;呂琳媛;;網絡重要節(jié)點排序方法綜述[J];科學通報;2014年13期

2 張宏毅;王立威;陳瑜希;;概率圖模型研究進展綜述[J];軟件學報;2013年11期

3 楊博;劉杰;劉大有;;基于隨機網絡集成模型的廣義網絡社區(qū)挖掘算法[J];自動化學報;2012年05期

本文編號：2559802