基于分層遞階的網(wǎng)絡(luò)結(jié)構(gòu)洞占據(jù)者挖掘研究.pdf

1、結(jié)構(gòu)洞最早是1992年由社會(huì)學(xué)家Burt提出的概念，在社會(huì)學(xué)領(lǐng)域有廣泛的研究。結(jié)構(gòu)洞是信息傳播中占據(jù)重要位置的一類(lèi)節(jié)點(diǎn)，是兩個(gè)非冗余的行動(dòng)者之間存在的缺口。如果兩個(gè)行動(dòng)者之間不存在直接連接，從整體上看來(lái)，這樣的缺口好像網(wǎng)絡(luò)的洞穴，因此社會(huì)學(xué)家將這樣的洞穴定義為結(jié)構(gòu)洞。網(wǎng)絡(luò)中占據(jù)結(jié)構(gòu)洞位置的節(jié)點(diǎn)具有控制信息傳播的優(yōu)勢(shì)，據(jù)研究，5％的結(jié)構(gòu)洞占據(jù)者控制著50％的信息傳播，在大型社交網(wǎng)絡(luò)Twitter上，1％的結(jié)構(gòu)洞占據(jù)者控制了25％的信息傳播

2、。最近幾年，挖掘結(jié)構(gòu)洞引起越來(lái)越多研究者的興趣，縱觀研究者們對(duì)于結(jié)構(gòu)洞問(wèn)題的研究主要是在單一粒度下對(duì)網(wǎng)絡(luò)結(jié)構(gòu)洞的挖掘與分析。然而很多真實(shí)網(wǎng)絡(luò)存在分層遞階的多粒度的社團(tuán)結(jié)構(gòu)特性，以往單一分析網(wǎng)絡(luò)的結(jié)構(gòu)洞只能反映整個(gè)網(wǎng)絡(luò)在一個(gè)層面的結(jié)構(gòu)洞信息。在研究商空間理論時(shí)，分層遞階的商空間模型是一種從多粒度的角度對(duì)問(wèn)題分析的思想，如果在挖掘網(wǎng)絡(luò)中結(jié)構(gòu)洞的問(wèn)題上，運(yùn)用這種分層遞階的思想，則能動(dòng)態(tài)地了解整個(gè)網(wǎng)絡(luò)中結(jié)構(gòu)洞的變化過(guò)程，使得這種多粒度結(jié)構(gòu)洞挖掘

3、更能反映真實(shí)網(wǎng)絡(luò)的狀況。因此本文結(jié)合單粒度下結(jié)構(gòu)洞算法的研究，提出了對(duì)多粒度下網(wǎng)絡(luò)結(jié)構(gòu)洞的挖掘和分析。
　　本文在伯特提出的結(jié)構(gòu)洞理論基礎(chǔ)上，提出了基于分層遞階粒計(jì)算的結(jié)構(gòu)洞挖掘方法。對(duì)于無(wú)權(quán)網(wǎng)絡(luò)，本文提出一種多粒度分層遞階結(jié)構(gòu)洞的挖掘方法HI-SH，并對(duì)不同粒度下的結(jié)構(gòu)洞挖掘分析。對(duì)于加權(quán)網(wǎng)絡(luò)，本文提出一種多粒度分層遞階的加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)洞的挖掘方法WHI-SH。
　　本文主要工作如下:
　　一、介紹結(jié)構(gòu)洞占據(jù)者的衡量指

4、標(biāo)和挖掘算法的研究現(xiàn)狀
　　從伯特提出結(jié)構(gòu)洞以來(lái)，結(jié)構(gòu)洞在社會(huì)學(xué)、醫(yī)學(xué)、計(jì)算機(jī)領(lǐng)域有了很大的發(fā)展，本文對(duì)結(jié)構(gòu)洞的衡量指標(biāo)進(jìn)行總結(jié)，包括有效規(guī)模、效率、約束度、等級(jí)度、pagerank值等;介紹用于挖掘結(jié)構(gòu)洞的算法，詳細(xì)介紹本文中用到的HIS算法、MAXD算法、W_HIS算法、W_CIHIS算法。
　　二、提出基于分層遞階結(jié)構(gòu)洞挖掘方法HI-SH
　　針對(duì)無(wú)權(quán)網(wǎng)絡(luò)，本文提出一種基于分層遞階的結(jié)構(gòu)洞挖掘方法HI-SH。首先

5、對(duì)網(wǎng)絡(luò)進(jìn)行多粒度分層遞階的社團(tuán)劃分，得到每一粒度下的社團(tuán)劃分結(jié)果;其次，根據(jù)兩級(jí)信息傳播理論，使用單一粒度下結(jié)構(gòu)洞挖掘算法，基于大量的統(tǒng)計(jì)規(guī)則，分別挖掘出每一粒度下前k％個(gè)結(jié)構(gòu)洞占據(jù)者，并記錄這些結(jié)構(gòu)洞占據(jù)者在不同粒度下的分層坐標(biāo)，分析結(jié)構(gòu)洞在不同粒度下的變化過(guò)程。最后，在科研合作網(wǎng)絡(luò)的公用數(shù)據(jù)Topic16和真實(shí)數(shù)據(jù)ICML_10上進(jìn)行實(shí)驗(yàn)，以及在社交網(wǎng)絡(luò)安青在線bbs的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，網(wǎng)絡(luò)的結(jié)構(gòu)洞是動(dòng)態(tài)變化的，單一粒度

6、下的結(jié)構(gòu)洞排名不能代表整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)洞排名。對(duì)于不同的網(wǎng)絡(luò)，并不存在某一特定的粒度，使得此粒度下網(wǎng)絡(luò)的結(jié)構(gòu)洞最優(yōu)。對(duì)于不同的網(wǎng)絡(luò)，粒度過(guò)粗或者粒度過(guò)細(xì)，網(wǎng)絡(luò)中結(jié)構(gòu)洞的影響力都沒(méi)有處于中間粒度的結(jié)構(gòu)洞的影響力高。
　　三、提出基于分層遞階的加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)洞挖掘方法WHI-SH
　　在接下來(lái)的工作中，為了研究網(wǎng)絡(luò)中邊的權(quán)重對(duì)網(wǎng)絡(luò)的性能的影響，從而造成對(duì)分層遞階結(jié)構(gòu)洞占據(jù)者的影響。文章在分層遞階的結(jié)構(gòu)洞挖掘方法的基礎(chǔ)上，在科研合作網(wǎng)

7、絡(luò)的研究中，進(jìn)一步考慮網(wǎng)絡(luò)中節(jié)點(diǎn)之間邊的權(quán)重，將商空間中分層遞階的思想應(yīng)用于加權(quán)的網(wǎng)絡(luò)結(jié)構(gòu)洞算法中，提出基于分層遞階的挖掘加權(quán)網(wǎng)絡(luò)的結(jié)構(gòu)洞方法WHI-SH。首先，對(duì)網(wǎng)絡(luò)中的邊給出一種計(jì)算權(quán)重的方式并為每條邊賦權(quán)值，對(duì)網(wǎng)絡(luò)進(jìn)行多粒度社團(tuán)劃分，得到每一粒度下的社團(tuán)劃分結(jié)果;然后，根據(jù)兩級(jí)信息傳播理論，用加權(quán)的結(jié)構(gòu)洞挖掘算法，挖掘出每一粒度下前k％個(gè)結(jié)構(gòu)洞;最后，在加權(quán)重處理后的科研合作網(wǎng)絡(luò)的公用數(shù)據(jù)Topic16+w和真實(shí)數(shù)據(jù)ICML_10