本文選題：社會(huì)網(wǎng)絡(luò) + 社團(tuán)挖掘��； 參考：《國(guó)防科學(xué)技術(shù)大學(xué)》2012年博士論文

【摘要】：社會(huì)網(wǎng)絡(luò)泛指由世界上具有復(fù)雜連接關(guān)系的、與研究目的相關(guān)的事物或?qū)ο笏M成的一種網(wǎng)絡(luò)，廣義上的社會(huì)網(wǎng)絡(luò)包括人際關(guān)系網(wǎng)絡(luò)、酶蛋白質(zhì)網(wǎng)絡(luò)、生物鏈網(wǎng)絡(luò)、新陳代謝網(wǎng)絡(luò)以及以互聯(lián)網(wǎng)為代表的各種社交網(wǎng)絡(luò)等。社會(huì)網(wǎng)絡(luò)可以抽象為一個(gè)具有復(fù)雜連接關(guān)系和結(jié)構(gòu)的可演化圖。通常，社團(tuán)是一組內(nèi)部連接緊密，外部連接稀疏的節(jié)點(diǎn)集合。社會(huì)網(wǎng)絡(luò)社團(tuán)挖掘?qū)τ诩訌?qiáng)對(duì)社會(huì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)理解、功能分析和行為預(yù)測(cè)具有重要的理論意義及實(shí)用價(jià)值，已被廣泛應(yīng)用于恐怖組織識(shí)別、新陳代謝路徑預(yù)測(cè)、蛋白質(zhì)相互作用網(wǎng)絡(luò)分析、搜索引擎開(kāi)發(fā)和網(wǎng)絡(luò)輿情監(jiān)控等諸多領(lǐng)域。 本文針對(duì)社團(tuán)挖掘的不同應(yīng)用場(chǎng)景，分別就多重圖模型下的社會(huì)網(wǎng)絡(luò)、含有不完全連接信息的社會(huì)網(wǎng)絡(luò)、二部圖模型下的社會(huì)網(wǎng)絡(luò)和多類(lèi)型節(jié)點(diǎn)組成的社會(huì)網(wǎng)絡(luò)的社團(tuán)挖掘關(guān)鍵技術(shù)進(jìn)行研究，主要貢獻(xiàn)有： 1、提出了一種基于層次化子圖樹(shù)的多重圖社會(huì)網(wǎng)絡(luò)社團(tuán)并行挖掘方法。根據(jù)多重圖數(shù)學(xué)模型，社會(huì)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間允許有多條連接邊，每條邊對(duì)應(yīng)于一個(gè)連接屬性，賦以一個(gè)自然數(shù)的權(quán)重。對(duì)于社會(huì)網(wǎng)絡(luò)圖中的任一子圖，本文運(yùn)用該數(shù)學(xué)模型，通過(guò)綜合該子圖各邊權(quán)重之和與節(jié)點(diǎn)個(gè)數(shù)引入子圖密度的概念，并基于從權(quán)重較低的邊出發(fā)進(jìn)行逐步分解的思想，構(gòu)造了子圖密度逐層遞增的層次化子圖樹(shù)HAT，提出了一種針對(duì)靜態(tài)社會(huì)網(wǎng)絡(luò)的層次化社團(tuán)并行分解更新算法。進(jìn)而，根據(jù)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)在相鄰時(shí)間段內(nèi)的局部變化原理，提出了針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的層次化社團(tuán)并行分解動(dòng)態(tài)更新算法。模擬數(shù)據(jù)集上的實(shí)驗(yàn)表明，以上算法在社團(tuán)挖掘的準(zhǔn)確度上優(yōu)于GN等同類(lèi)算法；數(shù)千萬(wàn)邊和節(jié)點(diǎn)規(guī)模的真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，以上算法適于高度并行計(jì)算，可以有效應(yīng)用于大數(shù)據(jù)社會(huì)網(wǎng)絡(luò)的社團(tuán)挖掘。 2、提出了基于節(jié)點(diǎn)親近度和馬氏距離的不完全信息社會(huì)網(wǎng)絡(luò)社團(tuán)挖掘方法。假設(shè)考察的社會(huì)網(wǎng)絡(luò)各節(jié)點(diǎn)具有相同的屬性，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)n維屬性值向量；節(jié)點(diǎn)之間的連接信息具有不完全性，即某些局部區(qū)域的某些連接未知。本文選取具有完全連接信息的某些區(qū)域作為學(xué)習(xí)的樣本區(qū)域，首先引入節(jié)點(diǎn)親近度的概念，任意一對(duì)節(jié)點(diǎn)的親近度由各自連接的鄰居數(shù)和公共鄰居數(shù)的某個(gè)經(jīng)驗(yàn)公式給出，親近度越接近于1，節(jié)點(diǎn)對(duì)越親近，為0的節(jié)點(diǎn)對(duì)視為不親近。接著對(duì)樣本區(qū)域的每個(gè)節(jié)點(diǎn)的n維值向量，乘以某個(gè)矩陣，將它們變換到一個(gè)稱(chēng)為馬氏空間的新空間中，使越親近的節(jié)點(diǎn)對(duì)，其值向量在馬氏空間中的距離，即馬氏距離越小。于是，問(wèn)題便轉(zhuǎn)化為能夠迭代求解的數(shù)學(xué)規(guī)劃問(wèn)題：尋找馬氏變換矩陣，使所有親近的節(jié)點(diǎn)對(duì)，其馬氏距離的親近度之加權(quán)和達(dá)到最小，同時(shí)使不親近的節(jié)點(diǎn)對(duì)的馬氏距離之和達(dá)到最大。最后，通過(guò)以上學(xué)習(xí)過(guò)程得到的馬氏矩陣，將整個(gè)社會(huì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)變換到馬氏空間中，經(jīng)貪婪搜索，給出一種基于節(jié)點(diǎn)馬氏距離的聚類(lèi)算法，以及一種-近似社團(tuán)啟發(fā)式分解方法。經(jīng)數(shù)千個(gè)節(jié)點(diǎn)規(guī)模的真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)，表明本文提出的方法和解決方案是有效的。 3、提出了基于圖像變換的二部圖社會(huì)網(wǎng)絡(luò)重疊社團(tuán)挖掘方法。二部圖社會(huì)網(wǎng)絡(luò)指由兩組子網(wǎng)組成的社會(huì)網(wǎng)絡(luò)，邊連接僅存在于不同子網(wǎng)的節(jié)點(diǎn)之間，子網(wǎng)內(nèi)部沒(méi)有任何邊連接。其社團(tuán)挖掘問(wèn)題是要找出那些分屬兩個(gè)子網(wǎng)的兩個(gè)社團(tuán)，稱(chēng)為社團(tuán)對(duì)，盡管社團(tuán)內(nèi)部各節(jié)點(diǎn)互不直接相連，卻與共同的對(duì)方社團(tuán)的節(jié)點(diǎn)有密切關(guān)聯(lián)。設(shè)兩組子網(wǎng)分別包含m個(gè)和n個(gè)節(jié)點(diǎn)，二部圖連接關(guān)系可以用一個(gè)m×n的0/1關(guān)系矩陣或黑白圖像描述。其社團(tuán)對(duì)的挖掘問(wèn)題轉(zhuǎn)化為：如何通過(guò)整行(列)圖像的不斷交換與調(diào)整，使圖像中的黑色像素點(diǎn)最大程度的聚合在一起。本文首先基于哈夫曼圖像編碼理論，，以信息量最小化為目標(biāo)，改進(jìn)了一種行(列)貪婪搜索與交換的雙聚類(lèi)迭代算法，使整幅圖像分解成若干矩形塊，找出那些黑像素點(diǎn)密度較高的塊，也就挖掘出了相應(yīng)的行社團(tuán)和列社團(tuán)。接著，進(jìn)一步針對(duì)某些行(列)節(jié)點(diǎn)可能同時(shí)屬于多個(gè)不同的行(列)社團(tuán)的應(yīng)用場(chǎng)景，提出了一種基于增益函數(shù)的重疊社團(tuán)模式搜索雙聚類(lèi)算法，其核心思想是，對(duì)于某一其它行(列)社團(tuán)的節(jié)點(diǎn)能否同時(shí)屬于本社團(tuán)，取決于該節(jié)點(diǎn)的加入能否使本行(列)社團(tuán)得到正收益，為此引入增益函數(shù)，它是新老社團(tuán)所對(duì)應(yīng)的塊狀區(qū)域密度差異的加權(quán)和。模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，算法具有良好的二部圖社團(tuán)挖掘效果。 4、提出了一種具有多類(lèi)型節(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò)社團(tuán)挖掘方法。在多類(lèi)型節(jié)點(diǎn)組成的社會(huì)網(wǎng)絡(luò)中，連接既存在于同類(lèi)節(jié)點(diǎn)之間，也存在于不同類(lèi)節(jié)點(diǎn)之間，而社團(tuán)組成僅限于同類(lèi)節(jié)點(diǎn)。具有n類(lèi)節(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò)的連接關(guān)系可以用n×(n+1)/2幅黑白圖像描述。本文首先將第一類(lèi)節(jié)點(diǎn)相關(guān)的n幅圖像拼接成一長(zhǎng)幅圖像，與第二類(lèi)節(jié)點(diǎn)相關(guān)的n-1幅剩余圖像也拼成一長(zhǎng)幅圖像，以此類(lèi)推。接著把社團(tuán)挖掘問(wèn)題轉(zhuǎn)化為與二部圖相似的長(zhǎng)幅圖像的行和列的交換問(wèn)題，其差異主要在于列交換時(shí)必須注意保持各列的語(yǔ)義一致性，其復(fù)雜性主要表現(xiàn)在需要綜合各長(zhǎng)幅圖像的黑像素點(diǎn)聚集度。本文運(yùn)用哈夫曼圖像編碼理論，以最大化壓縮描述上述所有圖像為目標(biāo)，分別在社團(tuán)數(shù)量已知和未知條件下，提出了相應(yīng)的多聚類(lèi)貪婪搜索算法。模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，算法在聚類(lèi)精度上優(yōu)于NMF等同類(lèi)算法。
[Abstract]:Social network refers to a kind of network composed of things or objects related to the purpose of research , such as interpersonal network , enzyme protein network , biological chain network , metabolic network and social networks represented by Internet .

In this paper , the key technologies of community mining of social network composed of the social network , the social network and the multi - type nodes under the multi - graph model are studied in this paper , which mainly contribute to the social network under the multi - graph model , the social network under the second graph model and the social network composed of the multi - type nodes .

1 . A multi - graph social network community parallel mining method based on hierarchical sub - graph tree is proposed . According to the multi - graph mathematical model , a plurality of connection edges are allowed between any two nodes in the social network .
Experiments on the real data sets of tens of millions of edges and nodes show that the above algorithm is suitable for highly parallel computing and can be used for community mining of large data social networks .

2 . An incomplete information social network association mining method based on node affinity and Markov distance is proposed . It is assumed that each node of the social network has the same attribute , and each node corresponds to an n - dimensional attribute value vector ;
In this paper , we choose some areas with complete connection information as the sample area of learning , first introduce the concept of node affinity , and then transform them into a new space called Markov model .

This paper proposes a two - cluster iterative algorithm based on image transformation , which is composed of two groups of sub - networks .

4 . A social network association mining method with many types of nodes is proposed . In a social network composed of many types of nodes , the connection exists between the same kind of nodes , but also exists between different nodes , and the association of the association can be described by n 脳 ( n + 1 ) / 2 black and white images .

【學(xué)位授予單位】：國(guó)防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2012
【分類(lèi)號(hào)】：TP393.09

【參考文獻(xiàn)】

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

1 萬(wàn)懷宇;林友芳;黃厚寬;;社會(huì)網(wǎng)絡(luò)中的鏈接穩(wěn)定性預(yù)測(cè)問(wèn)題研究[J];北京交通大學(xué)學(xué)報(bào);2009年05期

2 楊楠,弓丹志,李_

本文編號(hào)：1800348