鄧傳軍

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

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

中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0133-02

1 概述

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

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

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

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

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

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

（1）

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

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

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

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

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

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

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

（2）

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

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

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

4 結(jié)語

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

參考文獻(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

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

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

中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0133-02

1 概述

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

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

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

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

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

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

（1）

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

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

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

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

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

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

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

（2）

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

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

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

4 結(jié)語

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

參考文獻(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

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

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

中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0133-02

1 概述

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

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

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

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

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

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

（1）

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

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

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

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

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

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

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

（2）

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

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

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

4 結(jié)語

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

參考文獻(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