基于分層遞階的網絡結構洞占據(jù)者挖掘研究.pdf

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

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

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

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

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

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

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