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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 任曉龍;呂琳媛;;網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J];科學(xué)通報(bào);2014年13期

2 張宏毅;王立威;陳瑜希;;概率圖模型研究進(jìn)展綜述[J];軟件學(xué)報(bào);2013年11期

3 楊博;劉杰;劉大有;;基于隨機(jī)網(wǎng)絡(luò)集成模型的廣義網(wǎng)絡(luò)社區(qū)挖掘算法[J];自動(dòng)化學(xué)報(bào);2012年05期

本文編號(hào)：2559802