代表性社區(qū)集發(fā)現(xiàn)

武曉偉， 趙瓊

(復旦大學 軟件學院，上海 200433)

?

代表性社區(qū)集發(fā)現(xiàn)

武曉偉， 趙瓊

(復旦大學 軟件學院，上海 200433)

隨著計算機的普及和互聯(lián)網(wǎng)的快速發(fā)展，社交網(wǎng)絡(luò)的使用也越來越普遍。信息在社交網(wǎng)絡(luò)上呈爆炸式傳播，越來越多的熱門事件、網(wǎng)絡(luò)紅人在互聯(lián)網(wǎng)上出現(xiàn)，同時這些事件或者人物會通過聯(lián)系聚集為不同的群體或者社區(qū)，從而產(chǎn)生巨大的影響力。因此，互聯(lián)網(wǎng)、生物學、經(jīng)濟學等各類學科中的社區(qū)問題逐漸成了研究熱點，對社區(qū)進行研究發(fā)展成為了一個新興的方向。然而，進行社區(qū)發(fā)現(xiàn)后所得到的數(shù)據(jù)量仍是龐大的，因此，社區(qū)發(fā)現(xiàn)相關(guān)工作完成之后，對社區(qū)發(fā)現(xiàn)的結(jié)果進行優(yōu)化和進一步處理的相關(guān)研究也逐漸興起并且受到重視。為了達到以上目的，使社區(qū)及其相關(guān)理論能夠應(yīng)用到實際中，實現(xiàn)從理論到應(yīng)用的轉(zhuǎn)型，提出了代表性社區(qū)集發(fā)現(xiàn)算法。

社區(qū)發(fā)現(xiàn)； 代表性社區(qū)集； 鄰居節(jié)點覆蓋程度； Jaccard距離

0 引言

互聯(lián)網(wǎng)的快速發(fā)展讓信息獲取更為便捷和高效，鐵路網(wǎng)、城市公共交通網(wǎng)的不斷擴建讓居民出行更加方便，基因圖學的研究更為人體遺傳和人體構(gòu)造等揭開了神秘面紗，這種種的研究與進步都與復雜網(wǎng)絡(luò)息息相關(guān)。在現(xiàn)實生活中，微博、微信朋友圈、豆瓣、知乎、facebook、推特、電力網(wǎng)、生物學、基因圖譜、文獻引用、神經(jīng)網(wǎng)絡(luò)、演員關(guān)系等各類學科以及與個人生活緊密相關(guān)的應(yīng)用及事物都以復雜網(wǎng)絡(luò)為基礎(chǔ)。而在復雜網(wǎng)絡(luò)的研究中，社區(qū)發(fā)現(xiàn)的相關(guān)研究是早期便引起關(guān)注、得到重視的一個方向。

隨著社區(qū)發(fā)現(xiàn)的深入研究，對于社區(qū)質(zhì)量、社區(qū)多樣性等方面的要求越來越高。在社區(qū)中，高質(zhì)量的具有代表性的社區(qū)往往具有極為重要的現(xiàn)實意義。社區(qū)發(fā)現(xiàn)完成后，對社區(qū)的質(zhì)量、代表性等方面的研究，可以實現(xiàn)不同領(lǐng)域的訴求，是社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)、生物網(wǎng)絡(luò)等多個領(lǐng)域的熱門，更是社區(qū)研究的必然發(fā)展方向之一。

1 研究現(xiàn)狀

1.1 相關(guān)概念

復雜網(wǎng)絡(luò)可以認為是對一個復雜系統(tǒng)的抽象和描述方式，是呈現(xiàn)出高復雜度的網(wǎng)絡(luò)。我們可以將復雜網(wǎng)絡(luò)理解為一個通過連接來標識兩者之間是否具有聯(lián)系的一些個體的集合。復雜網(wǎng)絡(luò)雖然沒有明確的定義，但是我國著名科學家錢學森在上世紀80年代給出的復雜網(wǎng)絡(luò)的定義是認可度較高的。他給出的復雜網(wǎng)絡(luò)較為嚴格的定義是：具有自組織、自相似、吸引子、小世界、無標度中的一部分性質(zhì)或者全部性質(zhì)的網(wǎng)絡(luò)稱為復雜網(wǎng)絡(luò)。

社區(qū)到目前為止并沒有確定的定義，目前認可度較高的是由Newman和Girvan在2004年提出的社區(qū)定義[1]，認為社區(qū)是一個子圖，在這個子圖內(nèi)，節(jié)點與節(jié)點之間的聯(lián)系較為緊密，而該社區(qū)與其他社區(qū)之間的聯(lián)系較為稀疏。社區(qū)的存在能夠讓我們了解到生物網(wǎng)絡(luò)中新陳代謝的規(guī)律，社交網(wǎng)絡(luò)中用戶間的關(guān)系，論文網(wǎng)絡(luò)中互相引用的關(guān)系。更重要的是，通過對社區(qū)的研究，我們可以發(fā)現(xiàn)一些從單獨個體不能發(fā)現(xiàn)的一些特征和性質(zhì)，比如個體之間的內(nèi)在聯(lián)系等[2]。

1.2 研究水平及發(fā)展趨勢

隨著各類社區(qū)發(fā)現(xiàn)算法的不斷提出，國內(nèi)外對于社區(qū)發(fā)現(xiàn)的研究逐漸趨于成熟。在現(xiàn)有社區(qū)發(fā)現(xiàn)算法中，根據(jù)所處理的數(shù)據(jù)是圖、構(gòu)造樹，圖是有向圖或者無向圖，是否為加權(quán)圖等，子圖之間是否有重疊，又或者從圖的整體考慮或者從某一主要部分考慮等等方式，將社區(qū)發(fā)現(xiàn)的算法分為不同類別。在不同分類類別中，有一些較為經(jīng)典的，具有代表性的算法。

針對于如何提高社區(qū)發(fā)現(xiàn)的質(zhì)量，使其具有現(xiàn)實意義和應(yīng)用價值，各類學者也做了大量的研究。研究的通用做法一般是在社區(qū)發(fā)現(xiàn)的過程中，加入特定的需要考慮的因素，通過該因素使社區(qū)發(fā)現(xiàn)算法具有較好的運行效果，應(yīng)用在現(xiàn)實場景中。如為了使挖掘出的社區(qū)具有分值且該分值代表社區(qū)可獲得的效應(yīng)，Petko等人提出了在加權(quán)圖中，將最弱連接作為打分基準的思想[3]，該算法可應(yīng)用于對NBA球?qū)M行打分，以找出具有最佳配合效果的選手。Chekuri采用了數(shù)學方法解決分組問題[4]。Tianbao Yang等人在提取社區(qū)時，將連接關(guān)系與社區(qū)內(nèi)容結(jié)合，同時考慮兩者，考慮節(jié)點之間的連接關(guān)系如被引用、被指向等是具有意義的，可以代表與社區(qū)相關(guān)的屬性等，從而來提高社區(qū)發(fā)現(xiàn)的準確度，他們認為在復雜網(wǎng)絡(luò)中，連接關(guān)系與內(nèi)容都是不可或缺的一部分，否則會造成社區(qū)發(fā)現(xiàn)性能不佳[5]。

在不同社區(qū)發(fā)現(xiàn)過程中，結(jié)合其領(lǐng)域特征以及現(xiàn)實意義，加入不同的考慮因素，會使得該領(lǐng)域范圍內(nèi)挖掘出的社區(qū)質(zhì)量較高，符合實際要求，這是現(xiàn)有社區(qū)發(fā)現(xiàn)算法中，提高社區(qū)質(zhì)量的常見做法。

2 問題定義

2.1 應(yīng)用場景

在以往的研究中，我們意識到在進行社區(qū)發(fā)現(xiàn)研究的過程中，雖然將復雜網(wǎng)絡(luò)中連接緊密或者具有某方面共同性質(zhì)的節(jié)點劃分在同一個社區(qū)，但是即使進行劃分之后，所提取出的社區(qū)數(shù)目也是較多的。因此即使進行了社區(qū)發(fā)現(xiàn)，在一些情況下這些大量的社區(qū)也不利于現(xiàn)實分析和使用。例如，在Amazon的一個物品合作采購的復雜網(wǎng)絡(luò)中，其節(jié)點數(shù)量為334,863，邊的數(shù)量為925,872，通過社區(qū)發(fā)現(xiàn)算法獲得的社區(qū)數(shù)目高達75,149個[6]。因此如何從大量的社區(qū)中，提取出代表性的社區(qū)，是一個亟待解決的問題，它對于用戶進行決策，節(jié)省時間、人力、物力資源等具有非常重要的意義和作用，這也是本文進行研究的主要動機。

2.2 代表性社區(qū)集定義及性質(zhì)

以上問題的解決過程，可以總結(jié)為從大量的社區(qū)中，如何提取出代表性社區(qū)集，以幫助我們解決現(xiàn)實生活中所碰到的困難的過程，是具有一定的現(xiàn)實應(yīng)用場景的和現(xiàn)實意義的。本文所進行的關(guān)于代表性社區(qū)集發(fā)現(xiàn)的相關(guān)研究，是解決該類現(xiàn)實問題的一個途徑之一，具有重要的意義和作用。

代表性社區(qū)集：本文認為，代表性社區(qū)集是指在社區(qū)發(fā)現(xiàn)這一步驟完成之后，從若干個數(shù)量較大社區(qū)群中，選取出一個由k個社區(qū)組成的社區(qū)集合S，該集合S能夠最大程度的涵蓋整個社區(qū)群中不同類型社區(qū)的性質(zhì)，在一定程度上對該社區(qū)群的其他社區(qū)具有較大的影響力，是可以代表該社區(qū)群的一類社區(qū)集合。稱該集合S為代表性社區(qū)集。可以看出，代表性社區(qū)集發(fā)現(xiàn)的過程是最優(yōu)子集選取問題，可以將其歸約為NP-問題[7]。

在研究復雜網(wǎng)絡(luò)的社區(qū)分布情況時，為了將無數(shù)社區(qū)中的代表性社區(qū)集提取出來，基于以上的定義，本文認為代表性社區(qū)集應(yīng)該具有如下的性質(zhì)。

代表性社區(qū)集的性質(zhì)：

1) 若一個社區(qū)被選入代表性社區(qū)集，那該社區(qū)自身需要具有較高的質(zhì)量。

2) 相對于其他未被選入的社區(qū)，代表性社區(qū)集作為一個整體與其鄰居節(jié)點的連接應(yīng)該是更緊密的、其鄰居節(jié)點的數(shù)目應(yīng)是更多的，或者其鄰居節(jié)點在整個社區(qū)群中是更為重要的。我們稱該性質(zhì)為代表性社區(qū)集的鄰居節(jié)點覆蓋程度，是代表性社區(qū)集的一個屬性。即代表性社區(qū)集的鄰居節(jié)點覆蓋程度較高，該社區(qū)對其周圍社區(qū)的影響力較大。

3) 代表性社區(qū)集應(yīng)具有能夠體現(xiàn)整個社區(qū)群中不同社區(qū)類型的性質(zhì)，能代表大多數(shù)節(jié)點。對于整個社區(qū)群來說，其包含的社區(qū)數(shù)目眾多，類型也各有不同，不同的社區(qū)可能具有不同的含義或者特性，因此只有代表性社區(qū)集在最大程度上包含這些不同類型特性的社區(qū)，才具有普遍代表性，即代表性社區(qū)應(yīng)具有代表大多數(shù)節(jié)點或代表不同類型節(jié)點的特性。

我們可以將以上性質(zhì)認為是代表性社區(qū)集必備的性質(zhì)。具有這類性質(zhì)的社區(qū)在所有的社區(qū)中具有重要的意義，通過對該類代表性社區(qū)集的研究，可以對整個社區(qū)群的研究提供一定的支持。

2.3 代表性社區(qū)集發(fā)現(xiàn)

給定一個圖或者是一個社交網(wǎng)絡(luò)，用G=(V,E)來表示，V代表該圖中所有的點的集合，E代表該圖中所有邊的集合。定義該圖中的所有社區(qū)為C=(C1,C2,…,Cl),Ci?V,i≥1，這里的社區(qū)可以是重疊或非重疊社區(qū)。設(shè)代表性社區(qū)集某一性質(zhì)的評分函數(shù)為f(S)，則尋找代表性社區(qū)集的過程即是找到arg maxf(S)的值，通過尋找該值，最終獲得整個社區(qū)群的一個子集{Ci:i∈S?{1,2,…,l}}，其中|S|=k。

本文希望通過提出一個社區(qū)的評分函數(shù)來衡量和評估該社區(qū)是否具有代表性，是否將其選取到代表性社區(qū)集集合中，同時通過對應(yīng)的算法實現(xiàn)，解決在所有的社區(qū)中，尋找到社區(qū)個數(shù)為的代表性社區(qū)集的問題。

4 基于Jaccard距離的代表性社區(qū)集發(fā)現(xiàn)算法及改進

衡量一個代表性社區(qū)集是否具有代表性的一個方面是，該代表性社區(qū)集是否能夠最大程度的涵蓋整個集合即整個社區(qū)群中不同類型的社區(qū)。因此，在本章我們綜合考慮一個社區(qū)的自身質(zhì)量及其是否能夠包含不同類型社區(qū)的特性這兩個因素，提出了兩個基于Jaccard距離的代表性社區(qū)集挖掘算法。如果通過算法所獲得的代表性社區(qū)集能夠代表整個社區(qū)群中不同的社區(qū)類型，則該社區(qū)集才具有普遍代表性。因此本章除了考慮一個社區(qū)的自身質(zhì)量外，還引入了Jaccard距離來衡量被選入的社區(qū)集合是否具有普遍代表性。

綜合考慮一個社區(qū)自身質(zhì)量以及該社區(qū)是否能夠普遍代表其他節(jié)點，首先，假定最終得到的代表性社區(qū)集為{C:C1,C2,C3,…,Ck}，其中k≥1且為正整數(shù)。定義α為參數(shù)，其取值范圍為0≤α≤1，N(Ci)是社區(qū)Ci所有的鄰居節(jié)點，即N(Ci)={u∈V:?v∈Ci,(u,v)∈E}。N(Ci)∩N(Ci)與N(Ci)∪N(Ci)代表兩個社區(qū)Ci與Cj鄰居節(jié)點的交集與并集。E(Ci)是指Ci中節(jié)點之間邊的條數(shù)，|Ci|是Ci中節(jié)點的個數(shù)。q(Ci)代表該社區(qū)的質(zhì)量。g(Si,j)代表對是否選取Ci與Cj兩個集合的評分函數(shù)，則基于Jaccard距離的代表性社區(qū)集評分函數(shù)g(Si,j)如下定義為式(1)、(2)。

(1)

(2)

對于基于Jaccard距離的代表性社區(qū)集評分函數(shù)，初始時需要一次性選擇兩個社區(qū)，其初始值如式(3)。

(3)

我們可以知道，Jaccard距離滿足三角不等式，即對于任意的三個集合，i,j,p∈S，任意兩個社區(qū)的鄰居節(jié)點組成的集合N(Ci)與N(Cj)之間的Jaccard相似度為D(i,j)，則為式(4)。

(4)

首先，根據(jù)Jaccard距離滿足三角不等式，有如下關(guān)系：

D(i,j)+D(j,p)>D(i,p)

則對于評分函數(shù)g(Si,j)，有以下結(jié)論成立：

g(Si,j)+g(Sj,p)=

(q(Ci)+2q(Cj)+q(Cp))+

(q(Ci)+2q(Cj)+q(Cp))+α(D(i,j)+D(j,p))>(q(Ci)+q(Cp))+αD(i,p)=g(Si,p)?g(Si,j)+g(Sj,p)>g(Si,p)

基于Jaccard距離的評分函數(shù)滿足三角不等式，因此我們對尋找最大距離的貪心算法做一些變形，將其中的兩個點之間邊的權(quán)重轉(zhuǎn)化為兩個集合之間的質(zhì)量與Jaccard距離之和即g(Si,j)。利用離散p-擴散問題的相關(guān)概念，即如果其滿足三角不等式，我們可以通過使用尋找最大距離的貪心算法來解決該問題[8]，評分函數(shù)(2)同理可證。

5 基于鄰居節(jié)點覆蓋情況的代表性社區(qū)集發(fā)現(xiàn)算法

在社會學中，核心-邊緣結(jié)構(gòu)模型是一種較為經(jīng)典的理論模型，該模型由J. R. Friedmann提出。在該理論中，核心與邊緣之間存在著不平等的發(fā)展關(guān)系。簡單來說，核心部分具有統(tǒng)治地位，邊緣在發(fā)展上或者其他方面依賴于核心。在計算機科學的研究中，Jure Leskovec提出了AGM模型(Community-affiliation Graph Model)[9]，同時他闡釋了在一個復雜網(wǎng)絡(luò)中，核心-邊緣結(jié)構(gòu)是存在并且具有意義的。在復雜網(wǎng)絡(luò)結(jié)構(gòu)中有一部分是核心，這些核心部分具有和復雜網(wǎng)絡(luò)其他部分共有的特性，而除此之外其余邊緣的部分可以看作是“尾巴”，核心部分的鄰居節(jié)點覆蓋情況是決定該部分是否是核心的重要因素。因此在本文中，我們將核心-邊緣理論引入到算法中，利用該社會學概念，通過一個部分的鄰居節(jié)點覆蓋程度來衡量一個部分是否為核心部分，若鄰居節(jié)點覆蓋率較多或者覆蓋程度較高，那我們可以認為其能夠代表其他部分的特性，同時具有較強的影響力。

根據(jù)以上的性質(zhì)，在一個社區(qū)群中，我們綜合考慮其中某一個社區(qū)自身的質(zhì)量以及該社區(qū)的鄰居節(jié)點覆蓋情況，將這兩個因素作為挖掘代表性社區(qū)集的關(guān)鍵因素，提出如下基于鄰居節(jié)點覆蓋情況的代表性社區(qū)集發(fā)現(xiàn)算法。

基于鄰居節(jié)點覆蓋率的代表性社區(qū)集發(fā)現(xiàn)算法及其改進

我們綜合考慮一個社區(qū)的自身質(zhì)量以及其鄰居節(jié)點覆蓋率，首先，假定最終得到的代表性社區(qū)集為{Ci:i∈S?{1,2,…,l}}，其中S|=k，i≥1且為正整數(shù)。定義α為參數(shù)，其取值范圍為0≤α≤1，N(Ci)是社區(qū)Ci所有的鄰居節(jié)點，即N(Ci)={u∈V:?v∈Ci,(u,v)∈E}，E(Ci)是指Ci中節(jié)點之間邊的條數(shù)，|Ci|是Ci中節(jié)點的個數(shù)。q(Ci)代表該社區(qū)的質(zhì)量，我們這里將其定義為Ci內(nèi)部平均邊的條數(shù)。則基于鄰居節(jié)點覆蓋率的評分函數(shù)定義如式(5)、(6)。

(5)

(6)

其中，該函數(shù)的初始條件如式(7)。

f(S1)=q(C1)+αN(C1)

(7)

對于該評分函數(shù)(1)，我們可以證明其屬于次模態(tài)函數(shù)，證明過程如下。對于任意的集合S與T，其中S?T，且i?T，有以下證明過程成立：

(∪j∈SN(Cj))|≥q(Ci)+α|N(Ci)(∪j∈TN(Cj))|=f(T∪{i})-f(T)?f(S∪{i})-f(S)≥f(T∪{i})-f(T)

因此，該評分函數(shù)符合邊際遞減效應(yīng)，且該函數(shù)是非負函數(shù)，因此屬于次模態(tài)函數(shù)。因為q(Ci)與∪i∈SN(Ci)的數(shù)量級并不相同，所以我們在進行具體計算時會將其分別進行線性歸一化，將其轉(zhuǎn)化為無量綱表達式，利用線性歸一化后的值來進行計算。因為線性歸一化并不會改變函數(shù)的性質(zhì)，因此歸一化后，該函數(shù)仍然符合次模態(tài)函數(shù)的次模性。同理可證明評分函數(shù)(2)。

6 總結(jié)

論文首先介紹了社區(qū)、社區(qū)發(fā)現(xiàn)等基礎(chǔ)理論，綜述了前人在社區(qū)及社區(qū)發(fā)現(xiàn)方面的相關(guān)研究，總結(jié)、梳理并且分析了常見的社區(qū)發(fā)現(xiàn)方法，闡明了社區(qū)發(fā)現(xiàn)在現(xiàn)實生活中的實際應(yīng)用以及其重要意義。但是隨著研究的深入，提出了社區(qū)發(fā)現(xiàn)目前在應(yīng)用中的不足之處，針對該問題提出了研究代表性社區(qū)集發(fā)現(xiàn)的必要性和意義。

本文通過對社區(qū)進行深入的研究，提出了代表性社區(qū)集的定義，以及代表性社區(qū)所需具有的性質(zhì)，之后對代表性社區(qū)集發(fā)現(xiàn)進行建模。通過數(shù)學領(lǐng)域的次模態(tài)函數(shù)以及最大p-擴散問題模型的理論支撐，本文提出了兩類代表性社區(qū)發(fā)現(xiàn)算法：基于Jaccard距離的代表性社區(qū)集發(fā)現(xiàn)算法以及基于鄰居節(jié)點覆蓋情況的代表性社區(qū)集發(fā)現(xiàn)算法。在提出核心算法的同時，我們證明了這兩類代表性社區(qū)集發(fā)現(xiàn)算法具有數(shù)學理論支撐，從理論上來說具有可行性。

[1] Newman M E, M Girvan. Finding and evaluating community structure in networks[J]. Physical Review E (Statistical Nonlinear & Soft Matter Physics), 2004, 69(2): 026113-026113.

[2] Mucha, P.J., et al., Community structure in time-dependent, multiscale and multiplex networks[J]. Science, 2010, 328: 876-878.

[3] Bogdanov, P., et al., As Strong as the Weakest Link:Mining Diverse Cliques in Weighted Graphs[M]. Berlin Heidelberg Springer, 2013: 525-540.

[4] Chekuri, C., G. Even and G. Kortsarz, A greedy approximation algorithm for the group Steiner problem[J]. Discrete Applied Mathematics, 2006, 154(1): 15-34.

[5] Yang, T., et al., Combining Link and Content for Community Detection[M]. New York: Springer, 2014: 190-201.

[6] Held, P. and R. Online Community Detection by Using Nearest Hubs[J]. arXivpreprint arxrXiv: 2016, 1601.06527.

[7] 陳彬, 洪家榮，王亞東. 最優(yōu)特征子集選擇問題[J]. 計算機學報, 1997(2): 133-138.

[8] Hassin R S. Rubinstein, A Tamir. Approximation algorithms for maximum dispersion[J]. Operations Research Letters, 1997, 21(3): 133-137.

[9] Yang J, Leskovec J. Overlapping Communities Explain Core-Periphery Organization of Networks[J]. Proceedings of the IEEE, 2014, 102(12): 1892-1902.

Finding Representative Communities

Wu Xiaowei,Zhao Qiong

(Fudan University Software School， Shanghai 200433, China)

With the popularization of computer and rapid development of the Internet, the use of social networks is becoming more and more popular. Information in social networks is spreading explosively, increasingly popular events and web celebrities appear on the Internet. These events or people gather into different groups or communities through different connections, and produce enormous leverage. Therefore, communities of the Internet, biology, economics and other disciplines have become a hot topic of research gradually. Researches on the community have become a burgeoning area. The research on community belongs to complex network research area, it has irreplaceable significance in computer science, biology and other disciplines. However, the data size is still huge after community detection. Therefore, once the community detection is completed, how to optimize and what we can do to process the result further are aspects that are gradually on the rise and have been highly attached. In order to achieve the purpose, and to make the community and related theory applied to practice, this paper proposes the representative communities mining algorithm.

Community detection; Representative communities; Neighbor coverage; Jaccard distance

武曉偉(1992-)，男，碩士研究生，研究方向：電子商務(wù)與電子政務(wù)。 趙瓊(1991-)，女，碩士研究生，研究方向：電子商務(wù)與電子政務(wù)。

1007-757X(2017)07-0073-03

TG409

A

2017.03.01)