基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法研究

鄧傳軍

摘要：本文針對網(wǎng)絡(luò)一般算法存在問題，提出來一種基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法。該算法基于社會網(wǎng)絡(luò)中節(jié)點和邊的屬性進行有向加權(quán)社會網(wǎng)絡(luò)建模，融合節(jié)點之間相對重要性理論和網(wǎng)絡(luò)拓撲原理，共同發(fā)現(xiàn)加權(quán)的社會網(wǎng)絡(luò)中的重要節(jié)點。

關(guān)鍵詞：加權(quán) 節(jié)點 算法

中圖分類號：TP39 文獻標識碼：A 文章編號：1007-9416（2014）08-0133-02

1 概述

不管是社會網(wǎng)絡(luò)，還是WWW網(wǎng)絡(luò)，一般介紹的各種算法幾乎都是站在整體的角度，或顯式或隱式地對網(wǎng)絡(luò)中所有節(jié)點的重要性進行全局的排序，很少有學(xué)者關(guān)注網(wǎng)絡(luò)中節(jié)點的相對重要性。然而，在數(shù)學(xué)領(lǐng)域著名的“六度分割理論”形象地揭示了客觀世界存在普遍的聯(lián)系性。在客觀世界中，任何兩個個體之間哪怕是看起來毫不相干的兩者之間都是存在著各種潛在的關(guān)系。在對網(wǎng)絡(luò)節(jié)點重要性的研究方面，2000年Chang，Cohn和McCallum提出一種主體敏感性的HITS算法變種，之后人們受到他們的啟發(fā)提出了基于PageRank算法的個人主體敏感變種算法，雖然這些研究是主要是基于搜索引擎對搜索結(jié)果的優(yōu)化，要達到搜索內(nèi)容個人主體化的目標，但是他們的算法已經(jīng)為人們開啟了對網(wǎng)絡(luò)節(jié)點相對重要性研究的思想大門。

在研究了Scott White與Padhraic Smyth總結(jié)的相對重要性發(fā)現(xiàn)框架基礎(chǔ)上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權(quán)網(wǎng)絡(luò)，讓其對有向網(wǎng)絡(luò)也給予支持。下面給出我們對網(wǎng)絡(luò)節(jié)點相對重要性的定義。

定義1：給出圖G（V，E），根節(jié)點r和節(jié)點t，其中{r，t}G，我們定義非負值I（t|r）為節(jié)點t對于根節(jié)點r的相對重要性。

定義2：給出圖G（V，E），將T（G）中的節(jié)點相對于根節(jié)點r的重要度進行排序，I（T|r），其中TV。為了到達這一目的，我們先針對每個tT計算I（t|r）值，然后將值進行排序，其中I（t|r）值越大，則說明相對重要性越強。

定義3：給出圖G（V，E），一個待排序的節(jié)點集合T（G）與一個根節(jié)點集合R（G），其中RV，計算所有集合T中的節(jié)點對集合R的相對重要性，即I（T|R）。

這里與定義2中一樣，要計算I（T|R），其中rR，通常我們需要先分別計算{I（t|r），rR}。比如，我們可以用平均對集合R的相對重要性來定義I（t|R）：

（1）

如果不用平均值的話，我們也可以這樣定義I（t|R）=min{I（t|r）：rR}。

定義4：給出圖G（V，E），要求出說有節(jié)點的相對重要程度，我們只需將R與T都設(shè)置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應(yīng)用于大型網(wǎng)絡(luò)的小社區(qū)重要節(jié)點發(fā)現(xiàn)，而且可以進行全局重要節(jié)點挖掘。

2 對網(wǎng)絡(luò)節(jié)點權(quán)值的定義

對于雙加權(quán)社會網(wǎng)絡(luò)中節(jié)點權(quán)重的定義問題，國內(nèi)外學(xué)者們都曾從不同的角度給出很多種不同的定義，在本文中，我們主要考慮的是社會網(wǎng)絡(luò)，因此我需要更多的考慮是節(jié)點（大多時候是用戶或個體），在網(wǎng)絡(luò)中的聲望或者活躍情況。而社會網(wǎng)絡(luò)中某個節(jié)點越是活躍，他越是能夠帶動影響越多的節(jié)點，一起參與到網(wǎng)絡(luò)交互當中，故此我們可以用一個節(jié)點的活躍度來作為社會網(wǎng)絡(luò)節(jié)點的權(quán)值大小指標?；钴S度在社會網(wǎng)絡(luò)中的表現(xiàn)形式可以是打電話、發(fā)信息、聊天、聚餐、郊游等等，只要是發(fā)生在網(wǎng)絡(luò)中某個節(jié)點上的事件。我們都可以視為是該節(jié)點活躍度的一個展現(xiàn)方面，將這些事件進行網(wǎng)絡(luò)全局的歸一處理，即可得到我們在要的加權(quán)社會網(wǎng)絡(luò)節(jié)點的權(quán)值。結(jié)合上文所闡述的內(nèi)容，我們給出網(wǎng)絡(luò)節(jié)點權(quán)值的一般定義，設(shè)網(wǎng)絡(luò)個體i提交發(fā)布的總消息或資源等交互總數(shù)為Mi，使用該在線社交網(wǎng)絡(luò)平臺的時長為Ti（天）。則在網(wǎng)絡(luò)中該個體的活躍度可以被定義為。

然而，雖然上述定義能夠在一定程度上，描述該網(wǎng)絡(luò)個體的活躍情況，但是，在在線社交網(wǎng)絡(luò)中，很有可能會出現(xiàn)用戶注冊時間很短，卻在短時間內(nèi)大量的進行網(wǎng)絡(luò)交互行為，然而，往往絕大多數(shù)用戶是保持在一個較低的活躍度水平上的，由此可見該定義所描繪的活躍度，并不能更好的展現(xiàn)一個節(jié)點的真實活躍情況。

針對上述原因，我們提出一種新的加權(quán)網(wǎng)絡(luò)節(jié)點權(quán)值定義方法，定義如公式2所示。

（2）

其中為在近某一個標準時間段T內(nèi)，網(wǎng)絡(luò)個體i所發(fā)出的所有交互總數(shù)，為個體活躍度的調(diào)節(jié)因子。之所以如此定義，原因上文雖然提到一部分，然而，其主要原因是因為在實際處理真實網(wǎng)絡(luò)數(shù)據(jù)集時，我們遇到很多異常個體，為了讓所有網(wǎng)絡(luò)個體都能夠有個展現(xiàn)其活躍情況的刻畫指標，而且該活躍指標又不能因個體的差異產(chǎn)生較大的起伏，因此結(jié)合了數(shù)理歸一相關(guān)理論知識，我們將時間的概念弱化，采用統(tǒng)一時間段，這樣較少了變量，讓活躍度體現(xiàn)的就是該個體的真實活躍情況，并且通過調(diào)節(jié)因子，讓節(jié)點活躍度始終保持在大約0小于1的區(qū)間之內(nèi)，從而為下一步有向加權(quán)社會網(wǎng)絡(luò)的重要節(jié)點發(fā)現(xiàn)提供了堅實的理論基礎(chǔ)。

3 基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法

在該算法中，針對任一有向圖如圖1所示，我們將相連的兩節(jié)點對節(jié)點之間的重要度定義，并且令；對于不相鄰的任意兩節(jié)點，如節(jié)點與節(jié)點，可以看出從到的路徑集合包含{，，，}，將相鄰的節(jié)點間相對重要度定義為兩節(jié)點間的關(guān)系強度，這是因為關(guān)系強度是兩個用戶關(guān)注度和重要性的調(diào)和平均值，當兩值相差較大的時候，調(diào)和平均值會比他們的算術(shù)平均值更接近較小的那個值。當節(jié)點對節(jié)點交互較少，而節(jié)點對節(jié)點交互較多時，那么會造成單向的高強度關(guān)系，采用調(diào)和平均值能夠有效的避免這種情況的出現(xiàn)。另外，在的定義中采用所有用戶的平均交互次數(shù)作為全局因子，這一措施可以有效的克服小社區(qū)的高局部強度效應(yīng)。

4 結(jié)語

本文簡單介紹了國內(nèi)外學(xué)者提出的網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，對它們的優(yōu)缺點進行了對比討論分析。同時指出了這些算法對于發(fā)掘社會網(wǎng)絡(luò)中重要節(jié)點的局限性。提出了新的基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，新算法在雙加權(quán)與有向的基礎(chǔ)上，考慮節(jié)點與節(jié)點間緊密關(guān)系程度，節(jié)點個體的活躍度以及考慮了任意兩節(jié)點間的相對重要性。根據(jù)新算法提出了評估重要節(jié)點的指標，并對算法中的公式進行詳細的解釋，針對算法中任意節(jié)點間相對重要度，提出來k最短啟發(fā)式搜索子算法，并且給出了整體算法的實現(xiàn)流程圖。

參考文獻

[1]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用.北京：清華大學(xué)出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò).北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint

摘要：本文針對網(wǎng)絡(luò)一般算法存在問題，提出來一種基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法。該算法基于社會網(wǎng)絡(luò)中節(jié)點和邊的屬性進行有向加權(quán)社會網(wǎng)絡(luò)建模，融合節(jié)點之間相對重要性理論和網(wǎng)絡(luò)拓撲原理，共同發(fā)現(xiàn)加權(quán)的社會網(wǎng)絡(luò)中的重要節(jié)點。

關(guān)鍵詞：加權(quán) 節(jié)點 算法

中圖分類號：TP39 文獻標識碼：A 文章編號：1007-9416（2014）08-0133-02

1 概述

不管是社會網(wǎng)絡(luò)，還是WWW網(wǎng)絡(luò)，一般介紹的各種算法幾乎都是站在整體的角度，或顯式或隱式地對網(wǎng)絡(luò)中所有節(jié)點的重要性進行全局的排序，很少有學(xué)者關(guān)注網(wǎng)絡(luò)中節(jié)點的相對重要性。然而，在數(shù)學(xué)領(lǐng)域著名的“六度分割理論”形象地揭示了客觀世界存在普遍的聯(lián)系性。在客觀世界中，任何兩個個體之間哪怕是看起來毫不相干的兩者之間都是存在著各種潛在的關(guān)系。在對網(wǎng)絡(luò)節(jié)點重要性的研究方面，2000年Chang，Cohn和McCallum提出一種主體敏感性的HITS算法變種，之后人們受到他們的啟發(fā)提出了基于PageRank算法的個人主體敏感變種算法，雖然這些研究是主要是基于搜索引擎對搜索結(jié)果的優(yōu)化，要達到搜索內(nèi)容個人主體化的目標，但是他們的算法已經(jīng)為人們開啟了對網(wǎng)絡(luò)節(jié)點相對重要性研究的思想大門。

在研究了Scott White與Padhraic Smyth總結(jié)的相對重要性發(fā)現(xiàn)框架基礎(chǔ)上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權(quán)網(wǎng)絡(luò)，讓其對有向網(wǎng)絡(luò)也給予支持。下面給出我們對網(wǎng)絡(luò)節(jié)點相對重要性的定義。

定義1：給出圖G（V，E），根節(jié)點r和節(jié)點t，其中{r，t}G，我們定義非負值I（t|r）為節(jié)點t對于根節(jié)點r的相對重要性。

定義2：給出圖G（V，E），將T（G）中的節(jié)點相對于根節(jié)點r的重要度進行排序，I（T|r），其中TV。為了到達這一目的，我們先針對每個tT計算I（t|r）值，然后將值進行排序，其中I（t|r）值越大，則說明相對重要性越強。

定義3：給出圖G（V，E），一個待排序的節(jié)點集合T（G）與一個根節(jié)點集合R（G），其中RV，計算所有集合T中的節(jié)點對集合R的相對重要性，即I（T|R）。

這里與定義2中一樣，要計算I（T|R），其中rR，通常我們需要先分別計算{I（t|r），rR}。比如，我們可以用平均對集合R的相對重要性來定義I（t|R）：

（1）

如果不用平均值的話，我們也可以這樣定義I（t|R）=min{I（t|r）：rR}。

定義4：給出圖G（V，E），要求出說有節(jié)點的相對重要程度，我們只需將R與T都設(shè)置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應(yīng)用于大型網(wǎng)絡(luò)的小社區(qū)重要節(jié)點發(fā)現(xiàn)，而且可以進行全局重要節(jié)點挖掘。

2 對網(wǎng)絡(luò)節(jié)點權(quán)值的定義

對于雙加權(quán)社會網(wǎng)絡(luò)中節(jié)點權(quán)重的定義問題，國內(nèi)外學(xué)者們都曾從不同的角度給出很多種不同的定義，在本文中，我們主要考慮的是社會網(wǎng)絡(luò)，因此我需要更多的考慮是節(jié)點（大多時候是用戶或個體），在網(wǎng)絡(luò)中的聲望或者活躍情況。而社會網(wǎng)絡(luò)中某個節(jié)點越是活躍，他越是能夠帶動影響越多的節(jié)點，一起參與到網(wǎng)絡(luò)交互當中，故此我們可以用一個節(jié)點的活躍度來作為社會網(wǎng)絡(luò)節(jié)點的權(quán)值大小指標?；钴S度在社會網(wǎng)絡(luò)中的表現(xiàn)形式可以是打電話、發(fā)信息、聊天、聚餐、郊游等等，只要是發(fā)生在網(wǎng)絡(luò)中某個節(jié)點上的事件。我們都可以視為是該節(jié)點活躍度的一個展現(xiàn)方面，將這些事件進行網(wǎng)絡(luò)全局的歸一處理，即可得到我們在要的加權(quán)社會網(wǎng)絡(luò)節(jié)點的權(quán)值。結(jié)合上文所闡述的內(nèi)容，我們給出網(wǎng)絡(luò)節(jié)點權(quán)值的一般定義，設(shè)網(wǎng)絡(luò)個體i提交發(fā)布的總消息或資源等交互總數(shù)為Mi，使用該在線社交網(wǎng)絡(luò)平臺的時長為Ti（天）。則在網(wǎng)絡(luò)中該個體的活躍度可以被定義為。

然而，雖然上述定義能夠在一定程度上，描述該網(wǎng)絡(luò)個體的活躍情況，但是，在在線社交網(wǎng)絡(luò)中，很有可能會出現(xiàn)用戶注冊時間很短，卻在短時間內(nèi)大量的進行網(wǎng)絡(luò)交互行為，然而，往往絕大多數(shù)用戶是保持在一個較低的活躍度水平上的，由此可見該定義所描繪的活躍度，并不能更好的展現(xiàn)一個節(jié)點的真實活躍情況。

針對上述原因，我們提出一種新的加權(quán)網(wǎng)絡(luò)節(jié)點權(quán)值定義方法，定義如公式2所示。

（2）

其中為在近某一個標準時間段T內(nèi)，網(wǎng)絡(luò)個體i所發(fā)出的所有交互總數(shù)，為個體活躍度的調(diào)節(jié)因子。之所以如此定義，原因上文雖然提到一部分，然而，其主要原因是因為在實際處理真實網(wǎng)絡(luò)數(shù)據(jù)集時，我們遇到很多異常個體，為了讓所有網(wǎng)絡(luò)個體都能夠有個展現(xiàn)其活躍情況的刻畫指標，而且該活躍指標又不能因個體的差異產(chǎn)生較大的起伏，因此結(jié)合了數(shù)理歸一相關(guān)理論知識，我們將時間的概念弱化，采用統(tǒng)一時間段，這樣較少了變量，讓活躍度體現(xiàn)的就是該個體的真實活躍情況，并且通過調(diào)節(jié)因子，讓節(jié)點活躍度始終保持在大約0小于1的區(qū)間之內(nèi)，從而為下一步有向加權(quán)社會網(wǎng)絡(luò)的重要節(jié)點發(fā)現(xiàn)提供了堅實的理論基礎(chǔ)。

3 基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法

在該算法中，針對任一有向圖如圖1所示，我們將相連的兩節(jié)點對節(jié)點之間的重要度定義，并且令；對于不相鄰的任意兩節(jié)點，如節(jié)點與節(jié)點，可以看出從到的路徑集合包含{，，，}，將相鄰的節(jié)點間相對重要度定義為兩節(jié)點間的關(guān)系強度，這是因為關(guān)系強度是兩個用戶關(guān)注度和重要性的調(diào)和平均值，當兩值相差較大的時候，調(diào)和平均值會比他們的算術(shù)平均值更接近較小的那個值。當節(jié)點對節(jié)點交互較少，而節(jié)點對節(jié)點交互較多時，那么會造成單向的高強度關(guān)系，采用調(diào)和平均值能夠有效的避免這種情況的出現(xiàn)。另外，在的定義中采用所有用戶的平均交互次數(shù)作為全局因子，這一措施可以有效的克服小社區(qū)的高局部強度效應(yīng)。

4 結(jié)語

本文簡單介紹了國內(nèi)外學(xué)者提出的網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，對它們的優(yōu)缺點進行了對比討論分析。同時指出了這些算法對于發(fā)掘社會網(wǎng)絡(luò)中重要節(jié)點的局限性。提出了新的基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，新算法在雙加權(quán)與有向的基礎(chǔ)上，考慮節(jié)點與節(jié)點間緊密關(guān)系程度，節(jié)點個體的活躍度以及考慮了任意兩節(jié)點間的相對重要性。根據(jù)新算法提出了評估重要節(jié)點的指標，并對算法中的公式進行詳細的解釋，針對算法中任意節(jié)點間相對重要度，提出來k最短啟發(fā)式搜索子算法，并且給出了整體算法的實現(xiàn)流程圖。

參考文獻

[1]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用.北京：清華大學(xué)出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò).北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint

摘要：本文針對網(wǎng)絡(luò)一般算法存在問題，提出來一種基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法。該算法基于社會網(wǎng)絡(luò)中節(jié)點和邊的屬性進行有向加權(quán)社會網(wǎng)絡(luò)建模，融合節(jié)點之間相對重要性理論和網(wǎng)絡(luò)拓撲原理，共同發(fā)現(xiàn)加權(quán)的社會網(wǎng)絡(luò)中的重要節(jié)點。

關(guān)鍵詞：加權(quán) 節(jié)點 算法

中圖分類號：TP39 文獻標識碼：A 文章編號：1007-9416（2014）08-0133-02

1 概述

不管是社會網(wǎng)絡(luò)，還是WWW網(wǎng)絡(luò)，一般介紹的各種算法幾乎都是站在整體的角度，或顯式或隱式地對網(wǎng)絡(luò)中所有節(jié)點的重要性進行全局的排序，很少有學(xué)者關(guān)注網(wǎng)絡(luò)中節(jié)點的相對重要性。然而，在數(shù)學(xué)領(lǐng)域著名的“六度分割理論”形象地揭示了客觀世界存在普遍的聯(lián)系性。在客觀世界中，任何兩個個體之間哪怕是看起來毫不相干的兩者之間都是存在著各種潛在的關(guān)系。在對網(wǎng)絡(luò)節(jié)點重要性的研究方面，2000年Chang，Cohn和McCallum提出一種主體敏感性的HITS算法變種，之后人們受到他們的啟發(fā)提出了基于PageRank算法的個人主體敏感變種算法，雖然這些研究是主要是基于搜索引擎對搜索結(jié)果的優(yōu)化，要達到搜索內(nèi)容個人主體化的目標，但是他們的算法已經(jīng)為人們開啟了對網(wǎng)絡(luò)節(jié)點相對重要性研究的思想大門。

在研究了Scott White與Padhraic Smyth總結(jié)的相對重要性發(fā)現(xiàn)框架基礎(chǔ)上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權(quán)網(wǎng)絡(luò)，讓其對有向網(wǎng)絡(luò)也給予支持。下面給出我們對網(wǎng)絡(luò)節(jié)點相對重要性的定義。

定義1：給出圖G（V，E），根節(jié)點r和節(jié)點t，其中{r，t}G，我們定義非負值I（t|r）為節(jié)點t對于根節(jié)點r的相對重要性。

定義2：給出圖G（V，E），將T（G）中的節(jié)點相對于根節(jié)點r的重要度進行排序，I（T|r），其中TV。為了到達這一目的，我們先針對每個tT計算I（t|r）值，然后將值進行排序，其中I（t|r）值越大，則說明相對重要性越強。

定義3：給出圖G（V，E），一個待排序的節(jié)點集合T（G）與一個根節(jié)點集合R（G），其中RV，計算所有集合T中的節(jié)點對集合R的相對重要性，即I（T|R）。

這里與定義2中一樣，要計算I（T|R），其中rR，通常我們需要先分別計算{I（t|r），rR}。比如，我們可以用平均對集合R的相對重要性來定義I（t|R）：

（1）

如果不用平均值的話，我們也可以這樣定義I（t|R）=min{I（t|r）：rR}。

定義4：給出圖G（V，E），要求出說有節(jié)點的相對重要程度，我們只需將R與T都設(shè)置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應(yīng)用于大型網(wǎng)絡(luò)的小社區(qū)重要節(jié)點發(fā)現(xiàn)，而且可以進行全局重要節(jié)點挖掘。

2 對網(wǎng)絡(luò)節(jié)點權(quán)值的定義

對于雙加權(quán)社會網(wǎng)絡(luò)中節(jié)點權(quán)重的定義問題，國內(nèi)外學(xué)者們都曾從不同的角度給出很多種不同的定義，在本文中，我們主要考慮的是社會網(wǎng)絡(luò)，因此我需要更多的考慮是節(jié)點（大多時候是用戶或個體），在網(wǎng)絡(luò)中的聲望或者活躍情況。而社會網(wǎng)絡(luò)中某個節(jié)點越是活躍，他越是能夠帶動影響越多的節(jié)點，一起參與到網(wǎng)絡(luò)交互當中，故此我們可以用一個節(jié)點的活躍度來作為社會網(wǎng)絡(luò)節(jié)點的權(quán)值大小指標?；钴S度在社會網(wǎng)絡(luò)中的表現(xiàn)形式可以是打電話、發(fā)信息、聊天、聚餐、郊游等等，只要是發(fā)生在網(wǎng)絡(luò)中某個節(jié)點上的事件。我們都可以視為是該節(jié)點活躍度的一個展現(xiàn)方面，將這些事件進行網(wǎng)絡(luò)全局的歸一處理，即可得到我們在要的加權(quán)社會網(wǎng)絡(luò)節(jié)點的權(quán)值。結(jié)合上文所闡述的內(nèi)容，我們給出網(wǎng)絡(luò)節(jié)點權(quán)值的一般定義，設(shè)網(wǎng)絡(luò)個體i提交發(fā)布的總消息或資源等交互總數(shù)為Mi，使用該在線社交網(wǎng)絡(luò)平臺的時長為Ti（天）。則在網(wǎng)絡(luò)中該個體的活躍度可以被定義為。

然而，雖然上述定義能夠在一定程度上，描述該網(wǎng)絡(luò)個體的活躍情況，但是，在在線社交網(wǎng)絡(luò)中，很有可能會出現(xiàn)用戶注冊時間很短，卻在短時間內(nèi)大量的進行網(wǎng)絡(luò)交互行為，然而，往往絕大多數(shù)用戶是保持在一個較低的活躍度水平上的，由此可見該定義所描繪的活躍度，并不能更好的展現(xiàn)一個節(jié)點的真實活躍情況。

針對上述原因，我們提出一種新的加權(quán)網(wǎng)絡(luò)節(jié)點權(quán)值定義方法，定義如公式2所示。

（2）

其中為在近某一個標準時間段T內(nèi)，網(wǎng)絡(luò)個體i所發(fā)出的所有交互總數(shù)，為個體活躍度的調(diào)節(jié)因子。之所以如此定義，原因上文雖然提到一部分，然而，其主要原因是因為在實際處理真實網(wǎng)絡(luò)數(shù)據(jù)集時，我們遇到很多異常個體，為了讓所有網(wǎng)絡(luò)個體都能夠有個展現(xiàn)其活躍情況的刻畫指標，而且該活躍指標又不能因個體的差異產(chǎn)生較大的起伏，因此結(jié)合了數(shù)理歸一相關(guān)理論知識，我們將時間的概念弱化，采用統(tǒng)一時間段，這樣較少了變量，讓活躍度體現(xiàn)的就是該個體的真實活躍情況，并且通過調(diào)節(jié)因子，讓節(jié)點活躍度始終保持在大約0小于1的區(qū)間之內(nèi)，從而為下一步有向加權(quán)社會網(wǎng)絡(luò)的重要節(jié)點發(fā)現(xiàn)提供了堅實的理論基礎(chǔ)。

3 基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法

在該算法中，針對任一有向圖如圖1所示，我們將相連的兩節(jié)點對節(jié)點之間的重要度定義，并且令；對于不相鄰的任意兩節(jié)點，如節(jié)點與節(jié)點，可以看出從到的路徑集合包含{，，，}，將相鄰的節(jié)點間相對重要度定義為兩節(jié)點間的關(guān)系強度，這是因為關(guān)系強度是兩個用戶關(guān)注度和重要性的調(diào)和平均值，當兩值相差較大的時候，調(diào)和平均值會比他們的算術(shù)平均值更接近較小的那個值。當節(jié)點對節(jié)點交互較少，而節(jié)點對節(jié)點交互較多時，那么會造成單向的高強度關(guān)系，采用調(diào)和平均值能夠有效的避免這種情況的出現(xiàn)。另外，在的定義中采用所有用戶的平均交互次數(shù)作為全局因子，這一措施可以有效的克服小社區(qū)的高局部強度效應(yīng)。

4 結(jié)語

本文簡單介紹了國內(nèi)外學(xué)者提出的網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，對它們的優(yōu)缺點進行了對比討論分析。同時指出了這些算法對于發(fā)掘社會網(wǎng)絡(luò)中重要節(jié)點的局限性。提出了新的基于加權(quán)的社會網(wǎng)絡(luò)重要節(jié)點發(fā)現(xiàn)算法，新算法在雙加權(quán)與有向的基礎(chǔ)上，考慮節(jié)點與節(jié)點間緊密關(guān)系程度，節(jié)點個體的活躍度以及考慮了任意兩節(jié)點間的相對重要性。根據(jù)新算法提出了評估重要節(jié)點的指標，并對算法中的公式進行詳細的解釋，針對算法中任意節(jié)點間相對重要度，提出來k最短啟發(fā)式搜索子算法，并且給出了整體算法的實現(xiàn)流程圖。

參考文獻

[1]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用.北京：清華大學(xué)出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò).北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint