社交網(wǎng)絡(luò)的模糊進(jìn)化聚類算法研究
發(fā)布時(shí)間：2018-08-22 08:52
【摘要】：Facebook、Twitter、人人網(wǎng)、QQ社區(qū)、新浪微博等社交網(wǎng)絡(luò)服務(wù)平臺(tái)的成功推廣使關(guān)于社交網(wǎng)絡(luò)的研究正變得日益重要和廣泛。社區(qū)結(jié)構(gòu)是這些社交網(wǎng)絡(luò)的共同特性,所謂社區(qū)就是網(wǎng)絡(luò)中的“分組”,組內(nèi)聯(lián)系密切,組間聯(lián)系稀疏。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法大多是在靜態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)非重疊的社區(qū)結(jié)構(gòu),但現(xiàn)實(shí)世界中社交網(wǎng)絡(luò)往往隨著時(shí)間不斷推演而且社區(qū)結(jié)構(gòu)通�？梢灾丿B。本文在社交網(wǎng)絡(luò)環(huán)境下,研究模糊聚類算法和演(進(jìn))化聚類算法,從而完成重疊的和動(dòng)態(tài)的社區(qū)發(fā)現(xiàn)。聚類選取的初始點(diǎn)是否準(zhǔn)確對(duì)聚類效率和質(zhì)量都有影響。為在社交網(wǎng)絡(luò)聚類時(shí)采用準(zhǔn)確的初始點(diǎn),本文基于結(jié)構(gòu)洞和強(qiáng)弱關(guān)系理論,提出了社交網(wǎng)絡(luò)聚類中的初始點(diǎn)選擇算法SH_SW_IP和SH_SW_DP,這兩種算法綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性和節(jié)點(diǎn)間距離兩個(gè)指標(biāo)來獲得聚類初始點(diǎn),實(shí)驗(yàn)結(jié)果表明它們能以較低的時(shí)間復(fù)雜度得出較好的初始點(diǎn),并能在社區(qū)數(shù)目未知的情況下給出近似的社區(qū)數(shù)目。重疊社區(qū)發(fā)現(xiàn)是最近的研究熱點(diǎn),模糊聚類是其中一個(gè)重要方法。本文擴(kuò)展了強(qiáng)弱關(guān)系理論,并參照六度分隔理論構(gòu)造一種節(jié)點(diǎn)相似度,結(jié)合FCM算法框架并且采用SH_SW_IP算法確定聚類初始點(diǎn),重新設(shè)計(jì)一種局部最優(yōu)點(diǎn)獲取方案,從而利用該改進(jìn)的FCM算法實(shí)現(xiàn)社交網(wǎng)絡(luò)的模糊聚類,然后根據(jù)一定的標(biāo)準(zhǔn)設(shè)定閾值確定每個(gè)節(jié)點(diǎn)的類標(biāo),從而發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu),本文稱該算法為SCCFCM算法,對(duì)比實(shí)驗(yàn)結(jié)果表明SCCFCM算法在發(fā)現(xiàn)社區(qū)重疊結(jié)構(gòu)同時(shí)還可以發(fā)現(xiàn)每個(gè)社區(qū)的中心,而且隨著數(shù)據(jù)集的增大SCCFCM算法表現(xiàn)出更好的健壯性。動(dòng)態(tài)社區(qū)發(fā)現(xiàn)是最近社交網(wǎng)絡(luò)研究中的另一個(gè)熱點(diǎn),演(進(jìn))化聚類算法是它的一個(gè)重要方法,遺忘因子確定是演(進(jìn))化聚類中一個(gè)必要環(huán)節(jié)。本文在社交網(wǎng)絡(luò)中提出了節(jié)點(diǎn)慣性的概念,指出關(guān)鍵節(jié)點(diǎn)慣性變化規(guī)律,通過對(duì)比不同時(shí)間段的關(guān)鍵節(jié)點(diǎn)重要性得出遺忘因子的近似值,在確定了遺忘因子后利用演(進(jìn))化聚類框架改進(jìn)SCCFCM算法為ESCCFCM算法,使之能夠發(fā)現(xiàn)動(dòng)態(tài)的重疊社區(qū)。對(duì)比實(shí)驗(yàn)結(jié)果表明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.
【學(xué)位授予單位】：福州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：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.
【學(xué)位授予單位】：福州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.09;TP311.13
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 ;基于位置的手機(jī)社交網(wǎng)絡(luò)“貝多”正式發(fā)布[J];中國新通信;2008年06期
2 曹增輝;;社交網(wǎng)絡(luò)更偏向于用戶工具[J];信息網(wǎng)絡(luò);2009年11期
3 ;美國:印刷企業(yè)青睞社交網(wǎng)絡(luò)營銷新方式[J];中國包裝工業(yè);2010年Z1期
4 李智惠;柳承燁;;韓國移動(dòng)社交網(wǎng)絡(luò)服務(wù)的類型分析與促進(jìn)方案[J];現(xiàn)代傳播(中國傳媒大學(xué)學(xué)報(bào));2010年08期
5 賈富;;改變一切的社交網(wǎng)絡(luò)[J];互聯(lián)網(wǎng)天地;2011年04期
6 譚拯;;社交網(wǎng)絡(luò):連接與發(fā)現(xiàn)[J];廣東通信技術(shù);2011年07期
7 陳一舟;;社交網(wǎng)絡(luò)的發(fā)展趨勢(shì)[J];傳媒;2011年12期
8 殷樂;;全球社交網(wǎng)絡(luò)新態(tài)勢(shì)及文化影響[J];新聞與寫作;2012年01期
9 許麗;;社交網(wǎng)絡(luò):孤獨(dú)年代的集體狂歡[J];上海信息化;2012年09期
10 李玲麗;吳新年;;科研社交網(wǎng)絡(luò)的發(fā)展現(xiàn)狀及趨勢(shì)分析[J];圖書館學(xué)研究;2013年01期
相關(guān)會(huì)議論文 前10條
1 趙云龍;李艷兵;;社交網(wǎng)絡(luò)用戶的人格預(yù)測(cè)與關(guān)系強(qiáng)度研究[A];第七屆（2012）中國管理學(xué)年會(huì)商務(wù)智能分會(huì)場(chǎng)論文集（選編）[C];2012年
2 宮廣宇;李開軍;;對(duì)社交網(wǎng)絡(luò)中信息傳播的分析和思考——以人人網(wǎng)為例[A];首屆華中地區(qū)新聞與傳播學(xué)科研究生學(xué)術(shù)論壇獲獎(jiǎng)?wù)撐腫C];2010年
3 楊子鵬;喬麗娟;王夢(mèng)思;楊雪迎;孟子冰;張禹;;社交網(wǎng)絡(luò)與大學(xué)生焦慮緩解[A];心理學(xué)與創(chuàng)新能力提升——第十六屆全國心理學(xué)學(xué)術(shù)會(huì)議論文集[C];2013年
4 畢雪梅;;體育虛擬社區(qū)中的體育社交網(wǎng)絡(luò)解析[A];第九屆全國體育科學(xué)大會(huì)論文摘要匯編(4)[C];2011年
5 杜p，
本文編號(hào)：2196607
本文鏈接：http://www.sikaile.net/guanlilunwen/ydhl/2196607.html
最近更新
教材專著
