基于加權的社會網絡重要節點發現算法研究

鄧傳軍

摘要：本文針對網絡一般算法存在問題，提出來一種基于加權的社會網絡重要節點發現算法。該算法基于社會網絡中節點和邊的屬性進行有向加權社會網絡建模，融合節點之間相對重要性理論和網絡拓撲原理，共同發現加權的社會網絡中的重要節點。

關鍵詞：加權 節點 算法

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

1 概述

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

在研究了Scott White與Padhraic Smyth總結的相對重要性發現框架基礎上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權網絡，讓其對有向網絡也給予支持。下面給出我們對網絡節點相對重要性的定義。

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

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

定義3：給出圖G（V，E），一個待排序的節點集合T（G）與一個根節點集合R（G），其中RV，計算所有集合T中的節點對集合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），要求出說有節點的相對重要程度，我們只需將R與T都設置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應用于大型網絡的小社區重要節點發現，而且可以進行全局重要節點挖掘。

2 對網絡節點權值的定義

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

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

針對上述原因，我們提出一種新的加權網絡節點權值定義方法，定義如公式2所示。

（2）

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

3 基于加權的社會網絡重要節點發現算法

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

4 結語

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

參考文獻

[1]汪小帆，李翔，陳關榮.復雜網絡理論及其應用.北京：清華大學出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復雜系統與復雜網絡.北京：高等教育出版社，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

摘要：本文針對網絡一般算法存在問題，提出來一種基于加權的社會網絡重要節點發現算法。該算法基于社會網絡中節點和邊的屬性進行有向加權社會網絡建模，融合節點之間相對重要性理論和網絡拓撲原理，共同發現加權的社會網絡中的重要節點。

關鍵詞：加權 節點 算法

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

1 概述

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

在研究了Scott White與Padhraic Smyth總結的相對重要性發現框架基礎上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權網絡，讓其對有向網絡也給予支持。下面給出我們對網絡節點相對重要性的定義。

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

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

定義3：給出圖G（V，E），一個待排序的節點集合T（G）與一個根節點集合R（G），其中RV，計算所有集合T中的節點對集合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），要求出說有節點的相對重要程度，我們只需將R與T都設置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應用于大型網絡的小社區重要節點發現，而且可以進行全局重要節點挖掘。

2 對網絡節點權值的定義

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

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

針對上述原因，我們提出一種新的加權網絡節點權值定義方法，定義如公式2所示。

（2）

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

3 基于加權的社會網絡重要節點發現算法

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

4 結語

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

參考文獻

[1]汪小帆，李翔，陳關榮.復雜網絡理論及其應用.北京：清華大學出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復雜系統與復雜網絡.北京：高等教育出版社，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

摘要：本文針對網絡一般算法存在問題，提出來一種基于加權的社會網絡重要節點發現算法。該算法基于社會網絡中節點和邊的屬性進行有向加權社會網絡建模，融合節點之間相對重要性理論和網絡拓撲原理，共同發現加權的社會網絡中的重要節點。

關鍵詞：加權 節點 算法

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

1 概述

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

在研究了Scott White與Padhraic Smyth總結的相對重要性發現框架基礎上，我們對其中四種漸進問題的定義做了擴展，讓該框架不僅適用于加權網絡，讓其對有向網絡也給予支持。下面給出我們對網絡節點相對重要性的定義。

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

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

定義3：給出圖G（V，E），一個待排序的節點集合T（G）與一個根節點集合R（G），其中RV，計算所有集合T中的節點對集合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），要求出說有節點的相對重要程度，我們只需將R與T都設置為V，即R=T=V。

從上述對四種漸進問題的定義，我們不難看出該定義具有較強的適用性，不僅可以將該思想應用于大型網絡的小社區重要節點發現，而且可以進行全局重要節點挖掘。

2 對網絡節點權值的定義

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

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

針對上述原因，我們提出一種新的加權網絡節點權值定義方法，定義如公式2所示。

（2）

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

3 基于加權的社會網絡重要節點發現算法

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

4 結語

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

參考文獻

[1]汪小帆，李翔，陳關榮.復雜網絡理論及其應用.北京：清華大學出版社，2006：180-195.

[2]何大韌，劉宗華，汪秉宏.復雜系統與復雜網絡.北京：高等教育出版社，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