本文選題：社會網(wǎng)絡(luò) + 社團挖掘　； 參考：《國防科學技術(shù)大學》2012年博士論文

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

【學位授予單位】：國防科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2012
【分類號】：TP393.09

【參考文獻】

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

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

2 楊楠,弓丹志,李_

本文編號：1800348