本文選題：復雜網絡 + 社團結構探測　； 參考：《中央財經大學》2016年博士論文

【摘要】：復雜網絡理論為各學科領域中的復雜系統(tǒng)研究提供了簡單而有效的研究方法,在近十多年里得到了學術界的高度關注。不同領域中看似迥異的真實系統(tǒng)在不斷變化發(fā)展中會自然形成共同的特征,比如節(jié)點度的冪律度分布特征、小世界特征和社團結構特征等。由于突破了傳統(tǒng)還原論將對象孤立研究的局限性,復雜網絡能夠準確刻畫真實系統(tǒng)中的關鍵特征,本文研究的出發(fā)點就是網絡的社團結構特征。一方面復雜網絡中的社團結構可以對應于真實系統(tǒng)中自然形成的子系統(tǒng),比如蛋白質合作網絡會形成對應不同器官的功能模塊,科學家合作網絡會形成不同學科的研究群體,社交網絡會形成基于不同興趣愛好的俱樂部等。另一方面學術界對于復雜網絡社團結構的主流認識只停留在直觀層面,即把社團結構看作以更高概率相互連接的節(jié)點的集合,同時現有的社團結構探測算法也存在很多問題亟待解決,因此復雜網絡社團結構研究仍然是一個開放性的課題,研究其探測算法具有重要的理論意義和現實意義。類似于聚類算法,社團結構探測算法也屬于無監(jiān)督學習的范疇,其目標在于把網絡中的節(jié)點賦值到不同的社團中,因此基于聚類方法的理論框架提出社團結構探測算法是一個有前景的思路。密度聚類相比傳統(tǒng)聚類技術有天然的優(yōu)勢,比如DBSCAN相比K-means來說無需類簇個數作為先驗參數,不會落入局部最優(yōu)陷進,抗噪聲等,然而DBSCAN的聚類結果對兩個參數的取值非常敏感,因此密度聚類的參數選擇問題一直是機器學習領域亟待解決的難題。2014年發(fā)表在Science的論文中提出了新的密度聚類算法,即快速密度峰值算法(FDP:Fast Density Peak),該算法在保留DBSCAN優(yōu)點的同時巧妙的克服了其參數敏感問題,為無監(jiān)督學習提供了新的研究思路。受到這樣的啟發(fā),本文擬利用FDP算法探測復雜網絡中的社團結構。然而本文通過理論分析和數值實驗發(fā)現,由于網絡節(jié)點分布在極端高維空間中,導致FDP算法無法識別社團核心節(jié)點,從而無法直接應用于社團結構探測任務。除此之外,本文進一步發(fā)現當網絡結構變得模糊或社團數量過多時FDP算法的決策圖機制很難通過人機交互的方式準確識別社團個數�；谝陨蟽牲c事實,本文提出了基于流形學習框架的ISOFDP算法,該算法有效克服了網絡數據維數災難的問題從而使得社團核心點顯著區(qū)別于其它成員節(jié)點,同時提出了改進的分割密度函數以作為自動識別網絡社團個數的依據,最終ISOFDP算法相比經典算法取得了更好的社團結構探測結果。更進一步的,本文將ISOFDP算法框架進行推廣,分別提出了能夠探測重疊社團結構、有權有向網絡社團結構和動態(tài)網絡社團結構的算法,并取得了優(yōu)于經典算法的實驗結果。本論文的內容包括九章:第1章介紹了本論文的選題背景和研究意義,并說明了本論文的研究框架和創(chuàng)新點。第2章介紹了復雜網絡的基本理論和相關概念,然后對幾類社團結構探測算法進行了綜述。第3章分析了密度聚類算法fdp在探測社團結構時的缺陷,研究了克服其缺陷的方法之后提出了社團結構探測算法isofdp。第4章基于l-isomap、lle、le和lpp四種局部流形學習算法提出了快速社團結構探測算法,克服了isofdp計算性能低下的缺陷。第5章首先定義了非核心節(jié)點的社團隸屬度測度,根據節(jié)點隸屬度和閾值η的對比情況識別出網絡的重疊節(jié)點,以此提出能夠探測重疊社團結構的isofdpov算法。第6章基于信號理論的方法計算網絡節(jié)點的相似度測度,該相似度充分利用了網絡結構中連邊的權重和方向信息,以此為基礎提出了有權有向網絡的社團結構探測算法isofdpdw。第7章結合時間維度的信息利用3-階張量對所有時間點上的網絡序列建模得到鄰接張量,然后利用非負張量分解模型把鄰接張量分解為節(jié)點社團隸屬度矩陣和社團動態(tài)行為矩陣,以此求得動態(tài)社團張量,基于其各縱向切片探測各時間點上的社團結構和社團變化規(guī)律,最終提出了動態(tài)網絡社團結構探測算法tenfdp。第8章基于2006年6月16日至2014年7月9日中信行業(yè)指數收盤價日數據,計算指數收益率之間的相關系數并以此為連邊得到中信行業(yè)指數的平面最大過濾圖(pmfg)網絡,利用isofdpdw算法探測該網絡金融危機前中后三個階段的社團結構,以揭示金融危機對該網絡社團結構的影響。第9章對全文進行總結,并給出了本文現階段提出算法的缺點和不足,同時對本文算法的進一步推廣和改進工作進行了展望。本文的主要創(chuàng)新點包括以下幾個方面:第一,提出了一種基于密度聚類的社團結構探測算法isofdp。該算法無需社團個數作為先驗信息,且在準確度、參數敏感性和穩(wěn)健性3個方面都優(yōu)于經典算法。isofdp繼承了密度聚類算法fdp的優(yōu)點同時克服了其缺點。首先通過理論分析和數值實驗發(fā)現網絡節(jié)點具備高維數據的特點,即節(jié)點之間的距離高度同質化導致fdp無法識別社團核心節(jié)點,本文假設存在低維的本征維度可以保存原網絡的社團結構特征,提出使用經典流形學習算法isomap推斷出網絡在其本征維度上的映射,克服同質化距離的問題。本文進一步發(fā)現當網絡結構變得模糊或社團數量太多時,在fdp的決策圖上通過人機交互的方法無法正確識別社團個數,本文提出了改進的分割密度函數以自動識別社團個數,避免人機交互的過程。第二,提出了一種新的重疊社團結構探測算法ISOFDPOV。首先利用ISOFDP算法對網絡進行硬分割,可以得到社團核心節(jié)點以及每個社團的成員節(jié)點。本文定義了成員節(jié)點的社團隸屬度測度,該隸屬度測度可以衡量節(jié)點歸屬于某社團的強度,然后根據各成員節(jié)點關于各社團的隸屬度與閾值η的對比判斷成員節(jié)點的社團歸屬情況,社團歸屬不唯一的節(jié)點為重疊節(jié)點,從而找到網絡中的重疊社團結構。ISOFDPOV在人工和真實網絡上取得了相比經典算法更好的社團探測結果。第三,提出了有權有向網絡上的社團結構探測算法ISOFDPDW。首先分析了結構相似度只能利用二值對稱鄰接矩陣信息描述節(jié)點之間相似度的缺陷,提出使用信號相似度。信號相似度可以充分利用有權有向網絡中連邊的權重和方向信息,客觀描述節(jié)點之間的相似度。另外使用有權有向模塊度函數作為算法的收斂目標。最后在有權無向、無權有向和有權有向網絡上驗證了ISOFDPDW算法的有效性。第四,提出了基于非負張量分解模型的動態(tài)網絡社團結構探測算法TenFDP。該算法假設每個時間片上的社團結構不僅與當前網絡結構有關,還與上一時刻的社團結構有關。因此提出利用3-階張量模型對每個時間點上的網絡結構進行建模,得到領接張量以更好刻畫網絡結構隨時間的變化。利用非負張量分解模型把領接張量分解為節(jié)點社團隸屬度矩陣、社團動態(tài)行為矩陣,以此求得動態(tài)社團張量,基于該張量的每個縱向切片探測各時間點上的社團結構和社團變化規(guī)律。在5種類型的動態(tài)網絡上驗證了TenFDP算法的有效性。
[Abstract]:Complex network theory provides a simple and effective research method for the research of complex systems in the field of various disciplines. In the last more than 10 years, the academic circle has received high attention. The seemingly disparate real systems in different fields will naturally form the common characteristics in the changing development, such as the distribution of the power law degree of the node degree, the small world Characteristics and community structure characteristics. Because of the limitation of the traditional reductionism, the complex network can accurately depict the key features of the real system. The starting point of this study is the community structure characteristics of the network. On the one hand, the social solidarity structure in the complex network can correspond to the natural formation of the real system. The subsystems, such as the protein cooperation network, will form functional modules for different organs. The cooperative network of scientists will form different subjects, and social networks will form clubs based on different interests. On the other hand, the mainstream understanding of the complex structure of the complex network society is only in the visual level, that is, the society. The group structure is regarded as a set of nodes connected by higher probability, and there are many problems to be solved urgently. Therefore, the study of complex network community structure is still an open issue. It is of great theoretical meaning and practical significance to study its detection algorithm. The method of construction and measurement is also a category of unsupervised learning. Its goal is to assign nodes in the network to different societies. Therefore, it is a promising idea to propose a community structure detection algorithm based on the theoretical framework of clustering method. Density clustering has a natural advantage over traditional clustering techniques, such as DBSCAN compared with K-means. The number of clusters is required as a priori parameters, which will not fall into the local optimal trap and resist noise. However, the clustering results of DBSCAN are very sensitive to the values of the two parameters. Therefore, the parameter selection problem of density clustering has been a difficult problem to be solved in the field of machine learning. A new density clustering algorithm is proposed in the paper published in Science in.2014. The fast density peak algorithm (FDP:Fast Density Peak), which overcomes its parameter sensitivity while preserving the advantages of DBSCAN, provides new research ideas for unsupervised learning. Inspired by this, this paper uses FDP algorithm to detect the community structure in complex networks. However, this paper is based on theoretical analysis and numerical value. It is found that because the network nodes are distributed in extremely high dimensional space, the FDP algorithm can not identify the core nodes of the community, and can not be applied directly to the community structure detection task. In addition, this paper further finds that the decision drawing mechanism of the FDP algorithm is difficult to pass through human-computer interaction when the network structure becomes blurred or the number of societies is too large. Based on the above two facts, the ISOFDP algorithm based on the manifold learning framework is proposed in this paper. The algorithm effectively overcomes the problem of the network data dimension disaster and makes the community core distinctions distinctions from other member nodes. At the same time, the modified segmentation density function is proposed as an automatic identification network. According to the basis of the number of associations, the final ISOFDP algorithm has obtained a better detection result of the community structure compared with the classical algorithm. Further, this paper extends the framework of the ISOFDP algorithm, and puts forward the algorithms that can detect the overlapping community structure, have the right to the network community structure and the dynamic network community structure, and get better than the classic calculation. The contents of this paper include nine chapters: the first chapter introduces the background and significance of this thesis, and explains the research framework and innovation of this paper. The second chapter introduces the basic theory and related concepts of complex networks, and then summarizes several kinds of community structure detection algorithms. The third chapter analyzes density clustering. The defect of algorithm FDP in detecting community structure, and after studying the method to overcome its defects, we put forward the association structure detection algorithm isofdp. fourth chapter based on four local manifold learning algorithms, l-isomap, LLE, le and LPP, put forward the fast community structure detection algorithm, overcome the defects of the low performance of isofdp computing. In the fifth chapter, the non kernel is first defined. The degree of membership degree of the heart node is measured, and the overlapping nodes of the network are identified according to the degree of the node membership and the threshold value. The isofdpov algorithm that can detect the overlapping community structure is proposed. The sixth chapter calculates the similarity measure of the network nodes based on the signal theory. The similarity degree makes full use of the right of the edge of the network structure. Based on the information of weight and direction, this paper proposes a community structure detection algorithm with weighted directed networks isofdpdw. seventh chapter combined with the time dimension information using the 3- order tensor to build the adjacency tensor for the network sequence modeling at all time points, and then decomposes the adjacent tensor into the membership degree matrix of the node community by using the nonnegative tensor decomposition model. The dynamic community behavior matrix is used to obtain the dynamic community tensor. Based on its longitudinal slices, the community structure and the law of community change are detected. Finally, the dynamic network community structure detection algorithm tenfdp. eighth chapter is based on the closing price day data of the CITIC industry index from June 16, 2006 to July 9, 2014, and calculates the index income. The correlation coefficient between the rate and the PMFG network of the CITIC industry index is used to detect the community structure of the three stages of the network before the financial crisis by isofdpdw algorithm to reveal the impact of the financial crisis on the structure of the network community. The ninth chapter summarizes the full text and gives the present stage of this paper. The shortcomings and shortcomings of the algorithm are proposed, and the further promotion and improvement of the algorithm are prospected. The main innovation points of this paper include the following aspects: first, a community structure detection algorithm based on density clustering isofdp. is proposed, which does not need the number of communities as a priori information, and is sensitive to the parameters and is sensitive to parameters. The 3 aspects of nature and robustness are superior to the classical algorithm.Isofdp, which inherit the advantages of the density clustering algorithm FDP and overcome their shortcomings. First, the characteristics of the network nodes with high dimensional data are found through theoretical analysis and numerical experiments, that is, the homogeneity of the distance between nodes leads to the non method recognition of the core nodes of the community by FDP. This paper assumes the existence of the existence of the core nodes of the community. The low dimensional eigendimensions can preserve the community structure characteristics of the original network, and propose the use of the classical manifold learning algorithm Isomap to deduce the mapping of the network on its eigendimensions and overcome the problem of homogeneity distance. This paper further finds that when the network structure becomes blurred or the number of societies is too large, the interaction of human-computer interaction on the FDP's decision map is found. The method can not correctly identify the number of community. In this paper, an improved segmentation density function is proposed to automatically identify the number of communities and avoid the process of human-computer interaction. Second, a new overlapping community structure detection algorithm ISOFDPOV. is proposed, first of all, the ISOFDP algorithm is used to cut the network hard, and the core nodes of the community and each community can be obtained. The membership degree of member nodes is defined in this paper. The membership degree measure can measure the strength of the node belonging to a community. Then, according to the membership degree of each member's Association and the threshold value, the membership node is judged by the comparison of the membership degree. The overlapping community structure in the network.ISOFDPOV has been obtained on the artificial and real network, which is better than the classical algorithm. Third, the community structure detection algorithm on the weighted directed network ISOFDPDW. is proposed. First, the similarity degree of the structure similarity can only be described by the two value pair called adjacency matrix information. The signal similarity is used. The signal similarity can make full use of the weight and direction information of the connected edges in the network, and objectively describe the similarity between the nodes. In addition, the weighted directed modularity function is used as the convergence target of the algorithm. Finally, the ISOFD is proved to be unweighted and unauthorized and entitled to the network. The effectiveness of the PDW algorithm. Fourth, a dynamic network community structure detection algorithm based on the non negative tensor decomposition model TenFDP. is proposed. The algorithm assumes that the community structure on each time slice is not only related to the current network structure, but also is related to the community structure at the last time. Therefore, it is proposed to use the 3- order tensor model to the network at each time point. The network structure is modeled and the collar tensor is obtained to better describe the change of network structure with time. By using the nonnegative tensor decomposition model, the collar tensor is decomposed into the membership degree matrix of the node community, the dynamic behavior matrix of the community is used to obtain the dynamic community tensor, and the community structure on each time point of the tensor is detected based on each longitudinal section of the tensor. The effectiveness of the TenFDP algorithm is verified on 5 types of dynamic networks.

【學位授予單位】：中央財經大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：O157.5

【相似文獻】

相關期刊論文 前8條

1 張穎;陳其峰;曹小林;蔡靈倉;陳棟泉;盧鐵城;;微噴射粒子團簇探測算法及其應用[J];計算物理;2006年04期

2 袁斌;李敬宏;許琰;王弘X;;各向異性光源的輻射探測算法[J];計算物理;2007年03期

3 管志強;陳錢;錢惟賢;胡永生;;一種背景自適應調整的弱點目標探測算法[J];光學學報;2007年12期

4 雷震,吳玲達,老松楊;一種新的基于背景色度的鏡頭邊界探測算法[J];應用科學學報;2004年03期

5 楊曉云;梁鑫;岑敏儀;;適用于不規(guī)則DEM數據的粗差探測算法[J];自然科學進展;2007年04期

6 郭婕;劉軍;王寶林;;基于機器視覺的早期火焰探測算法研究[J];西北大學學報(自然科學版);2008年04期

7 葉錫恩;毛科益;夏銀水;;一種新的用于探測Pure Reed-Muller邏輯的算法[J];浙江大學學報(理學版);2007年03期

8 吳林林;;新一代天氣雷達冰雹探測算法及在業(yè)務中的應用[J];氣象;2006年01期

相關會議論文 前3條

1 唐文杰;駱志剛;陸斌;李聰;;一種基于高光譜壓縮數據的亞像元級目標探測算法[A];中國通信學會第六屆學術年會論文集（下）[C];2009年

2 陳南;;智能建筑中火災信息探測算法分析及應用[A];中國儀器儀表學會測控技術在資源節(jié)約和環(huán)境保護中的應用學術會議論文集[C];2001年

3 張輝;李國輝;陳俊;;一種基于新聞要素建模的新事件探測方法[A];第七屆和諧人機環(huán)境聯(lián)合學術會議（HHME2011)論文集【oral】[C];2011年

相關重要報紙文章 前1條

1 摩托羅拉公司提供;信號探測算法 提高藍牙性能 降低干擾[N];電子資訊時報;2002年

相關博士學位論文 前1條

1 游濤;基于密度聚類的復雜網絡社團結構探測算法與應用[D];中央財經大學;2016年

相關碩士學位論文 前10條

1 陳曉燕;基于多級探測算法的人體意外跌倒檢測裝置的開發(fā)[D];新疆大學;2015年

2 藍方宇;基于微攝動與步態(tài)特征的人體探測算法研究[D];電子科技大學;2014年

3 高孝杰;引入空間信息的高光譜目標探測算法研究[D];成都理工大學;2016年

4 王賓賓;基于混合系統(tǒng)的航空器中期沖突探測方法研究[D];中國民航大學;2014年

5 牛進保;位置社會網絡中重疊群組探測算法研究及并行化實現[D];華中科技大學;2015年

6 沈曉敏;光學分子影像仿真平臺中探測算法的研究與實現[D];西安電子科技大學;2012年

7 呂曾望;非授權局域網拓撲探測算法的研究與實現[D];國防科學技術大學;2004年

8 秦薇薇;基于紅外視頻的火災探測算法研究[D];西安建筑科技大學;2012年

9 馬磊;大規(guī)模網絡社團探測算法應用[D];華東師范大學;2012年

10 彭罡;強光背景下小目標探測算法研究[D];國防科學技術大學;2007年

，

本文編號：1820166