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

武曉偉， 趙瓊

(復(fù)旦大學(xué) 軟件學(xué)院，上海 200433)

?

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

武曉偉， 趙瓊

(復(fù)旦大學(xué) 軟件學(xué)院，上海 200433)

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

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

0 引言

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

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

1 研究現(xiàn)狀

1.1 相關(guān)概念

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

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

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

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

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

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

2 問題定義

2.1 應(yīng)用場(chǎng)景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

(4)

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

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

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

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

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

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

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

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

(5)

(6)

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

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

(7)

對(duì)于該評(píng)分函數(shù)(1)，我們可以證明其屬于次模態(tài)函數(shù)，證明過程如下。對(duì)于任意的集合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)

因此，該評(píng)分函數(shù)符合邊際遞減效應(yīng)，且該函數(shù)是非負(fù)函數(shù)，因此屬于次模態(tài)函數(shù)。因?yàn)閝(Ci)與∪i∈SN(Ci)的數(shù)量級(jí)并不相同，所以我們?cè)谶M(jìn)行具體計(jì)算時(shí)會(huì)將其分別進(jìn)行線性歸一化，將其轉(zhuǎn)化為無量綱表達(dá)式，利用線性歸一化后的值來進(jìn)行計(jì)算。因?yàn)榫€性歸一化并不會(huì)改變函數(shù)的性質(zhì)，因此歸一化后，該函數(shù)仍然符合次模態(tài)函數(shù)的次模性。同理可證明評(píng)分函數(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)實(shí)生活中的實(shí)際應(yīng)用以及其重要意義。但是隨著研究的深入，提出了社區(qū)發(fā)現(xiàn)目前在應(yīng)用中的不足之處，針對(duì)該問題提出了研究代表性社區(qū)集發(fā)現(xiàn)的必要性和意義。

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

[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]. 計(jì)算機(jī)學(xué)報(bào), 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)