社交網(wǎng)絡的模糊進化聚類算法研究
發(fā)布時間：2018-08-22 08:52
【摘要】：Facebook、Twitter、人人網(wǎng)、QQ社區(qū)、新浪微博等社交網(wǎng)絡服務平臺的成功推廣使關于社交網(wǎng)絡的研究正變得日益重要和廣泛。社區(qū)結構是這些社交網(wǎng)絡的共同特性,所謂社區(qū)就是網(wǎng)絡中的“分組”,組內(nèi)聯(lián)系密切,組間聯(lián)系稀疏。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法大多是在靜態(tài)網(wǎng)絡中發(fā)現(xiàn)非重疊的社區(qū)結構,但現(xiàn)實世界中社交網(wǎng)絡往往隨著時間不斷推演而且社區(qū)結構通�？梢灾丿B。本文在社交網(wǎng)絡環(huán)境下,研究模糊聚類算法和演(進)化聚類算法,從而完成重疊的和動態(tài)的社區(qū)發(fā)現(xiàn)。聚類選取的初始點是否準確對聚類效率和質(zhì)量都有影響。為在社交網(wǎng)絡聚類時采用準確的初始點,本文基于結構洞和強弱關系理論,提出了社交網(wǎng)絡聚類中的初始點選擇算法SH_SW_IP和SH_SW_DP,這兩種算法綜合考慮網(wǎng)絡中節(jié)點的重要性和節(jié)點間距離兩個指標來獲得聚類初始點,實驗結果表明它們能以較低的時間復雜度得出較好的初始點,并能在社區(qū)數(shù)目未知的情況下給出近似的社區(qū)數(shù)目。重疊社區(qū)發(fā)現(xiàn)是最近的研究熱點,模糊聚類是其中一個重要方法。本文擴展了強弱關系理論,并參照六度分隔理論構造一種節(jié)點相似度,結合FCM算法框架并且采用SH_SW_IP算法確定聚類初始點,重新設計一種局部最優(yōu)點獲取方案,從而利用該改進的FCM算法實現(xiàn)社交網(wǎng)絡的模糊聚類,然后根據(jù)一定的標準設定閾值確定每個節(jié)點的類標,從而發(fā)現(xiàn)網(wǎng)絡中的重疊社區(qū)結構,本文稱該算法為SCCFCM算法,對比實驗結果表明SCCFCM算法在發(fā)現(xiàn)社區(qū)重疊結構同時還可以發(fā)現(xiàn)每個社區(qū)的中心,而且隨著數(shù)據(jù)集的增大SCCFCM算法表現(xiàn)出更好的健壯性。動態(tài)社區(qū)發(fā)現(xiàn)是最近社交網(wǎng)絡研究中的另一個熱點,演(進)化聚類算法是它的一個重要方法,遺忘因子確定是演(進)化聚類中一個必要環(huán)節(jié)。本文在社交網(wǎng)絡中提出了節(jié)點慣性的概念,指出關鍵節(jié)點慣性變化規(guī)律,通過對比不同時間段的關鍵節(jié)點重要性得出遺忘因子的近似值,在確定了遺忘因子后利用演(進)化聚類框架改進SCCFCM算法為ESCCFCM算法,使之能夠發(fā)現(xiàn)動態(tài)的重疊社區(qū)。對比實驗結果表明ESCCFCM算法發(fā)現(xiàn)的社區(qū)不僅具有較高的模塊度而且能表現(xiàn)出更好的光滑性。
[Abstract]:The successful promotion of social networking services such as Facebook Twitter, Renren's QQ community and Sina Weibo makes research on social networks increasingly important and widespread. The community structure is the common characteristic of these social networks. The so-called community is the "grouping" in the network. Most of the traditional community discovery algorithms find non-overlapping community structures in static networks, but in the real world social networks tend to evolve over time and the community structures usually overlap. In this paper, fuzzy clustering algorithm and forward clustering algorithm are studied in the social network environment, so as to achieve overlapping and dynamic community discovery. Whether the initial point of clustering selection is accurate or not has an effect on clustering efficiency and quality. In order to use accurate initial points in the clustering of social networks, this paper is based on the theory of structure hole and strong / weak relation. In this paper, the initial point selection algorithms SH_SW_IP and SHSWADS in the clustering of social networks are proposed. These two algorithms consider the importance of nodes and the distance between nodes to obtain the initial points of clustering. The experimental results show that they can get a better initial point with lower time complexity and can give the approximate number of communities when the number of communities is unknown. Overlapping community discovery is a hot topic recently, and fuzzy clustering is one of the important methods. In this paper, the theory of strong and weak relation is extended, and a node similarity is constructed by referring to the six-degree separation theory. Combining with the framework of FCM algorithm and using SH_SW_IP algorithm to determine the initial point of clustering, a local optimum acquisition scheme is redesigned. The improved FCM algorithm is used to realize the fuzzy clustering of social network, and then the threshold is set according to a certain standard to determine the class label of each node, and the overlapping community structure in the network is found. This algorithm is called the SCCFCM algorithm in this paper. The experimental results show that the SCCFCM algorithm can find the community overlap structure and the center of each community at the same time, and the SCCFCM algorithm shows better robustness with the increase of the data set. Dynamic community discovery is another hot topic in the research of social network recently. The (progressive) clustering algorithm is one of its important methods, and the determination of forgetting factor is a necessary link in the (progressive) clustering. In this paper, the concept of node inertia is put forward in social networks, and the law of inertia variation of key nodes is pointed out. By comparing the importance of key nodes in different time periods, the approximate value of forgetting factor is obtained. After determining the forgetting factor, the SCCFCM algorithm is improved to ESCCFCM algorithm by using the (progressive) clustering framework, so that it can find the dynamic overlapping community. The experimental results show that the community discovered by ESCCFCM algorithm not only has higher modularity but also has better smoothness.
【學位授予單位】：福州大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP393.09;TP311.13
[Abstract]:The successful promotion of social networking services such as Facebook Twitter, Renren's QQ community and Sina Weibo makes research on social networks increasingly important and widespread. The community structure is the common characteristic of these social networks. The so-called community is the "grouping" in the network. Most of the traditional community discovery algorithms find non-overlapping community structures in static networks, but in the real world social networks tend to evolve over time and the community structures usually overlap. In this paper, fuzzy clustering algorithm and forward clustering algorithm are studied in the social network environment, so as to achieve overlapping and dynamic community discovery. Whether the initial point of clustering selection is accurate or not has an effect on clustering efficiency and quality. In order to use accurate initial points in the clustering of social networks, this paper is based on the theory of structure hole and strong / weak relation. In this paper, the initial point selection algorithms SH_SW_IP and SHSWADS in the clustering of social networks are proposed. These two algorithms consider the importance of nodes and the distance between nodes to obtain the initial points of clustering. The experimental results show that they can get a better initial point with lower time complexity and can give the approximate number of communities when the number of communities is unknown. Overlapping community discovery is a hot topic recently, and fuzzy clustering is one of the important methods. In this paper, the theory of strong and weak relation is extended, and a node similarity is constructed by referring to the six-degree separation theory. Combining with the framework of FCM algorithm and using SH_SW_IP algorithm to determine the initial point of clustering, a local optimum acquisition scheme is redesigned. The improved FCM algorithm is used to realize the fuzzy clustering of social network, and then the threshold is set according to a certain standard to determine the class label of each node, and the overlapping community structure in the network is found. This algorithm is called the SCCFCM algorithm in this paper. The experimental results show that the SCCFCM algorithm can find the community overlap structure and the center of each community at the same time, and the SCCFCM algorithm shows better robustness with the increase of the data set. Dynamic community discovery is another hot topic in the research of social network recently. The (progressive) clustering algorithm is one of its important methods, and the determination of forgetting factor is a necessary link in the (progressive) clustering. In this paper, the concept of node inertia is put forward in social networks, and the law of inertia variation of key nodes is pointed out. By comparing the importance of key nodes in different time periods, the approximate value of forgetting factor is obtained. After determining the forgetting factor, the SCCFCM algorithm is improved to ESCCFCM algorithm by using the (progressive) clustering framework, so that it can find the dynamic overlapping community. The experimental results show that the community discovered by ESCCFCM algorithm not only has higher modularity but also has better smoothness.
【學位授予單位】：福州大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP393.09;TP311.13
【相似文獻】
相關期刊論文 前10條
1 ;基于位置的手機社交網(wǎng)絡“貝多”正式發(fā)布[J];中國新通信;2008年06期
2 曹增輝;;社交網(wǎng)絡更偏向于用戶工具[J];信息網(wǎng)絡;2009年11期
3 ;美國:印刷企業(yè)青睞社交網(wǎng)絡營銷新方式[J];中國包裝工業(yè);2010年Z1期
4 李智惠;柳承燁;;韓國移動社交網(wǎng)絡服務的類型分析與促進方案[J];現(xiàn)代傳播(中國傳媒大學學報);2010年08期
5 賈富;;改變一切的社交網(wǎng)絡[J];互聯(lián)網(wǎng)天地;2011年04期
6 譚拯;;社交網(wǎng)絡:連接與發(fā)現(xiàn)[J];廣東通信技術;2011年07期
7 陳一舟;;社交網(wǎng)絡的發(fā)展趨勢[J];傳媒;2011年12期
8 殷樂;;全球社交網(wǎng)絡新態(tài)勢及文化影響[J];新聞與寫作;2012年01期
9 許麗;;社交網(wǎng)絡:孤獨年代的集體狂歡[J];上海信息化;2012年09期
10 李玲麗;吳新年;;科研社交網(wǎng)絡的發(fā)展現(xiàn)狀及趨勢分析[J];圖書館學研究;2013年01期
相關會議論文 前10條
1 趙云龍;李艷兵;;社交網(wǎng)絡用戶的人格預測與關系強度研究[A];第七屆（2012）中國管理學年會商務智能分會場論文集（選編）[C];2012年
2 宮廣宇;李開軍;;對社交網(wǎng)絡中信息傳播的分析和思考——以人人網(wǎng)為例[A];首屆華中地區(qū)新聞與傳播學科研究生學術論壇獲獎論文[C];2010年
3 楊子鵬;喬麗娟;王夢思;楊雪迎;孟子冰;張禹;;社交網(wǎng)絡與大學生焦慮緩解[A];心理學與創(chuàng)新能力提升——第十六屆全國心理學學術會議論文集[C];2013年
4 畢雪梅;;體育虛擬社區(qū)中的體育社交網(wǎng)絡解析[A];第九屆全國體育科學大會論文摘要匯編(4)[C];2011年
5 杜p，
本文編號：2196607
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/2196607.html
最近更新
教材專著
