社會(huì)關(guān)系網(wǎng)絡(luò)分析基礎(chǔ)理論：現(xiàn)狀與展望

鄧小龍，李欲曉，曾　潔

(1.北京郵電大學(xué) 可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100876；2.北京郵電大學(xué) 科學(xué)技術(shù)發(fā)展研究院,北京 100876)

?

社會(huì)關(guān)系網(wǎng)絡(luò)分析基礎(chǔ)理論：現(xiàn)狀與展望

鄧小龍1，李欲曉1，曾潔2

(1.北京郵電大學(xué) 可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100876；2.北京郵電大學(xué) 科學(xué)技術(shù)發(fā)展研究院,北京 100876)

摘要：針對(duì)關(guān)系結(jié)構(gòu)、網(wǎng)絡(luò)群體、網(wǎng)絡(luò)信息這3個(gè)社會(huì)關(guān)系網(wǎng)絡(luò)核心點(diǎn)，總結(jié)了社會(huì)關(guān)系網(wǎng)絡(luò)的基本概念、分類、組成要素、社會(huì)關(guān)系網(wǎng)絡(luò)分析的統(tǒng)計(jì)特性指標(biāo)、社團(tuán)結(jié)構(gòu)劃分算法等5個(gè)方面的主要問(wèn)題和研究現(xiàn)狀，并對(duì)未來(lái)與公共安全緊密相關(guān)的社會(huì)關(guān)系網(wǎng)絡(luò)上的結(jié)構(gòu)特性判別、多語(yǔ)言復(fù)雜情感環(huán)境下社會(huì)關(guān)系網(wǎng)絡(luò)中信息語(yǔ)義和傾向性判別，以及社會(huì)關(guān)系網(wǎng)絡(luò)信息傳播過(guò)程中心理互動(dòng)規(guī)律等方面的發(fā)展趨勢(shì)進(jìn)行了展望。

關(guān)鍵詞：社會(huì)關(guān)系網(wǎng)絡(luò)；分類；組成要素；統(tǒng)計(jì)特性指標(biāo)；社團(tuán)結(jié)構(gòu)劃分；個(gè)體及群體互動(dòng)

隨著互聯(lián)網(wǎng)在全球快速發(fā)展和社會(huì)信息化進(jìn)程加速，互聯(lián)網(wǎng)、手機(jī)等新媒體承載終端快速普及，極大方便了人們之間的信息傳遞和分享。這種社交網(wǎng)絡(luò)具體應(yīng)用形式反映了人與人之間的本質(zhì)社會(huì)關(guān)系，是人與人之間真實(shí)社會(huì)關(guān)系網(wǎng)絡(luò)在多種信息媒體上的具體投影和多維度展現(xiàn)。

同時(shí)，隨著當(dāng)代信息化、全球化進(jìn)程的進(jìn)一步加速以及全球恐怖主義活動(dòng)的進(jìn)一步升溫，大數(shù)據(jù)[1]、移動(dòng)互聯(lián)網(wǎng)、云計(jì)算等新技術(shù)也不斷出現(xiàn)，以社交網(wǎng)絡(luò)具體應(yīng)用形式為代表的社會(huì)關(guān)系網(wǎng)絡(luò)正深刻影響人們的生活方式和公共安全，因此對(duì)近年來(lái)蓬勃發(fā)展的社會(huì)關(guān)系網(wǎng)絡(luò)分析的相關(guān)理論進(jìn)行細(xì)節(jié)梳理，可以對(duì)未來(lái)科學(xué)界對(duì)社會(huì)關(guān)系網(wǎng)絡(luò)這一重要社會(huì)形態(tài)的發(fā)展趨勢(shì)進(jìn)行把握，并對(duì)社會(huì)關(guān)系網(wǎng)絡(luò)分析有著積極的推動(dòng)和促進(jìn)作用。當(dāng)前已有社會(huì)關(guān)系網(wǎng)絡(luò)分析的相關(guān)基礎(chǔ)理論主要有：①社會(huì)關(guān)系網(wǎng)絡(luò)基本概念及其與復(fù)雜網(wǎng)絡(luò)的關(guān)系；②社會(huì)關(guān)系網(wǎng)絡(luò)分類；③社會(huì)關(guān)系網(wǎng)絡(luò)組成要素；④社會(huì)關(guān)系網(wǎng)絡(luò)分析統(tǒng)計(jì)特性指標(biāo)；⑤社會(huì)關(guān)系網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分算法；⑥社會(huì)關(guān)系網(wǎng)絡(luò)個(gè)體及群體互動(dòng)。

1社會(huì)關(guān)系網(wǎng)絡(luò)基本概念及其與復(fù)雜網(wǎng)絡(luò)的關(guān)系

1.1社會(huì)關(guān)系網(wǎng)絡(luò)的基本概念

對(duì)于社會(huì)關(guān)系網(wǎng)絡(luò)的定義，劉軍[2]指出社會(huì)關(guān)系網(wǎng)絡(luò)是社會(huì)行動(dòng)者及其之間關(guān)系的集合，羅家德[3]指出社會(huì)關(guān)系網(wǎng)的相關(guān)理論是一個(gè)“中層理論”，有一組分析社會(huì)現(xiàn)象的概念，包括社會(huì)關(guān)系、社會(huì)網(wǎng)、關(guān)系強(qiáng)度、關(guān)系內(nèi)涵、網(wǎng)絡(luò)結(jié)構(gòu)、信任、社會(huì)資本、情感支持、人際影響等。

而近年來(lái)隨著互聯(lián)網(wǎng)的興起和美國(guó)Facebook、國(guó)內(nèi)開(kāi)心網(wǎng)、校內(nèi)網(wǎng)等“在線社交網(wǎng)絡(luò)”理念風(fēng)靡全球，研究者更多地從在線社交網(wǎng)絡(luò)的角度去考慮社會(huì)關(guān)系網(wǎng)絡(luò)，有學(xué)者[4-5]指出在線社交網(wǎng)絡(luò)是一種在信息網(wǎng)絡(luò)上由社會(huì)個(gè)體集合及個(gè)體間連接關(guān)系構(gòu)成的社會(huì)性結(jié)構(gòu)，包含關(guān)系結(jié)構(gòu)、網(wǎng)絡(luò)群體與網(wǎng)絡(luò)信息3個(gè)要素。其中，社交網(wǎng)絡(luò)的關(guān)系結(jié)構(gòu)是社會(huì)個(gè)體成員之間通過(guò)社會(huì)關(guān)系結(jié)成的網(wǎng)絡(luò)系統(tǒng)。個(gè)體也稱節(jié)點(diǎn)，可以是組織、個(gè)人、網(wǎng)絡(luò)ID 等不同含義的實(shí)體或虛擬個(gè)體；而個(gè)體間的相互關(guān)系可以是親友、動(dòng)作行為、收發(fā)消息等多種關(guān)系。

從社會(huì)關(guān)系網(wǎng)絡(luò)形式化定義而言，社會(huì)關(guān)系網(wǎng)絡(luò)可以抽象為一個(gè)由結(jié)點(diǎn)以及結(jié)點(diǎn)之間的邊組成的圖結(jié)構(gòu)：G=(V，e)，其中V為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，e為邊的集合。節(jié)點(diǎn)的個(gè)數(shù)N=|V|，邊的條數(shù)L=|e|。

在研究社會(huì)關(guān)系網(wǎng)絡(luò)的相關(guān)特性時(shí)，圖結(jié)構(gòu)一般分為有向圖、無(wú)向圖、無(wú)權(quán)圖、有權(quán)圖。如果在圖G中，只考慮結(jié)點(diǎn)和結(jié)點(diǎn)之間是否有邊存在，而不考慮邊權(quán)重，這時(shí)將圖G稱為無(wú)權(quán)圖，可以用N×N的鄰接矩陣A來(lái)描述圖G，對(duì)于?vi,vj∈V，如果兩個(gè)結(jié)點(diǎn)之間存在邊連接，則?eij∈e，Aij=1，否則Aij=0。而對(duì)于有權(quán)圖G=(V,e)，如果定義邊eij的權(quán)重為wij(wij屬于權(quán)重集合W并且wij為有效數(shù)值，一般為整數(shù)或者實(shí)數(shù))，則鄰接矩陣中表示邊eij的元素Aij=wij。

1.2與復(fù)雜網(wǎng)絡(luò)的關(guān)系

復(fù)雜網(wǎng)絡(luò)的概念和定義模型涵蓋社會(huì)關(guān)系網(wǎng)絡(luò)的相關(guān)定義，復(fù)雜網(wǎng)絡(luò)是指近年來(lái)在規(guī)模日益增大的萬(wàn)維網(wǎng)、電信網(wǎng)、移動(dòng)通訊網(wǎng)絡(luò)中可獲得的社會(huì)關(guān)系網(wǎng)絡(luò)數(shù)據(jù)，而這些社會(huì)關(guān)系網(wǎng)絡(luò)數(shù)據(jù)由于規(guī)模過(guò)于龐大使得人們無(wú)法通過(guò)傳統(tǒng)的技術(shù)和方法進(jìn)行管理和運(yùn)作，并且這些網(wǎng)絡(luò)都具有某些共同的性質(zhì)，比如“整體稀疏，局部密集；頂點(diǎn)度數(shù)服從冪率分布的無(wú)尺度特性[6]。再如，依據(jù)GIRVAN等[7]的觀點(diǎn)，現(xiàn)實(shí)網(wǎng)絡(luò)中的復(fù)雜網(wǎng)絡(luò)大致分為4類：社會(huì)關(guān)系網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)。這4種網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)形式各不相同，彼此描述的系統(tǒng)內(nèi)涵各異，其節(jié)點(diǎn)和邊的定義差別也很大，但其卻具有一些相同的特征：節(jié)點(diǎn)度服從冪律分布，群聚系數(shù)高，節(jié)點(diǎn)間平均路徑距離小，因此研究者常使用復(fù)雜網(wǎng)絡(luò)的相關(guān)概念和模型對(duì)社會(huì)關(guān)系網(wǎng)絡(luò)進(jìn)行研究。

2社會(huì)關(guān)系網(wǎng)絡(luò)分類

通常而言，社會(huì)關(guān)系網(wǎng)絡(luò)中往往表現(xiàn)為線上群體和線下群體兩種模式，線上社會(huì)關(guān)系網(wǎng)絡(luò)群體為在互聯(lián)網(wǎng)媒體中所反映出來(lái)的社會(huì)關(guān)系群體，即在論壇、社交網(wǎng)絡(luò)、即時(shí)通信工具中聯(lián)系緊密的社會(huì)關(guān)系群體。依據(jù)2008年12月歐盟關(guān)于社會(huì)計(jì)算的研究報(bào)告《Key areas in the public sector impact of social computing》，在線社會(huì)關(guān)系網(wǎng)絡(luò)群體可分為4類：①即時(shí)消息類應(yīng)用，即通過(guò)在線實(shí)時(shí)通信平臺(tái)進(jìn)行交互的社會(huì)關(guān)系網(wǎng)絡(luò)，如MSN、QQ、AIM、飛信、微信等；②在線社交類應(yīng)用，即通過(guò)在線社交關(guān)系進(jìn)行溝通的社會(huì)關(guān)系網(wǎng)絡(luò)，如Facebook、Google+、人人網(wǎng)、開(kāi)心網(wǎng)、QQ空間等；③微博類應(yīng)用，即雙向短信息發(fā)布平臺(tái)進(jìn)行溝通的社會(huì)關(guān)系網(wǎng)絡(luò)，如Twitter、新浪微博、騰訊微博、網(wǎng)易微博、搜狐微博等；④共享空間等其他類應(yīng)用，即通過(guò)其他可以相互溝通但結(jié)合不緊密的Web2.0應(yīng)用進(jìn)行交流的社會(huì)關(guān)系網(wǎng)絡(luò)，如論壇、博客、BBS、視頻分享、社會(huì)書(shū)簽、在線購(gòu)物等。

而線下社會(huì)關(guān)系網(wǎng)絡(luò)群體是通過(guò)傳統(tǒng)的互聯(lián)網(wǎng)非實(shí)時(shí)方式進(jìn)行溝通和交流的社會(huì)關(guān)系網(wǎng)絡(luò)，如郵件網(wǎng)絡(luò)、語(yǔ)言溝通網(wǎng)絡(luò)、手機(jī)呼叫網(wǎng)絡(luò)、手機(jī)短消息網(wǎng)絡(luò)等，強(qiáng)調(diào)通過(guò)傳統(tǒng)的面對(duì)面溝通或書(shū)信等方式進(jìn)行溝通。

3社會(huì)關(guān)系網(wǎng)絡(luò)組成要素

通過(guò)對(duì)社會(huì)關(guān)系網(wǎng)絡(luò)的組成要素進(jìn)行邏輯抽象，可以發(fā)現(xiàn)社會(huì)關(guān)系網(wǎng)絡(luò)通常由點(diǎn)、關(guān)系、角色和演化4個(gè)核心組成要素構(gòu)成。

(1)點(diǎn)：社會(huì)關(guān)系網(wǎng)絡(luò)中的點(diǎn)是發(fā)生聯(lián)系的事物。對(duì)于社會(huì)網(wǎng)絡(luò)而言，點(diǎn)是行動(dòng)者，可以是任何一個(gè)社會(huì)單位或社會(huì)實(shí)體。它既可以是一個(gè)教育機(jī)構(gòu)如教研室、學(xué)院、學(xué)校；也可以是一個(gè)村落、組織、城市、國(guó)家；還可以是一個(gè)微博賬號(hào)、一個(gè)Facebook賬號(hào)等。關(guān)于點(diǎn)的信息既可以是動(dòng)態(tài)的，也可以是靜態(tài)的。

(2)關(guān)系：關(guān)系是社會(huì)關(guān)系網(wǎng)絡(luò)中點(diǎn)與點(diǎn)之間的聯(lián)系。關(guān)系常常代表具體的聯(lián)絡(luò)內(nèi)容或者現(xiàn)實(shí)中發(fā)生的實(shí)質(zhì)性關(guān)系。關(guān)系有多種表現(xiàn)，首先，點(diǎn)與點(diǎn)之間的關(guān)系類型多樣，可以是朋友關(guān)系、上下級(jí)關(guān)系、國(guó)際貿(mào)易關(guān)系、城市距離關(guān)系等。其次，兩個(gè)點(diǎn)之間的關(guān)系還有可能是“多元關(guān)系”。例如兩個(gè)學(xué)生之間可能同時(shí)存在同學(xué)關(guān)系、友誼關(guān)系、戀愛(ài)關(guān)系和上下級(jí)關(guān)系。對(duì)多元關(guān)系網(wǎng)絡(luò)的研究，是當(dāng)前社會(huì)關(guān)系網(wǎng)絡(luò)分析中最具潛力的前沿領(lǐng)域。再次，兩個(gè)點(diǎn)之間的關(guān)系還具有顯式和隱式(比如微博用戶的關(guān)注關(guān)系)、雙向和單向、強(qiáng)和弱等區(qū)別。除此之外，研究者還廣泛研究了關(guān)系的特征，比如互惠性、傳遞性、同質(zhì)性、異質(zhì)性等。

(3)角色：角色是社會(huì)關(guān)系網(wǎng)絡(luò)中的點(diǎn)在某個(gè)特定的關(guān)系中所具有的責(zé)任或任務(wù)。比如在某個(gè)社會(huì)團(tuán)體中，可能領(lǐng)導(dǎo)者與下級(jí)聯(lián)系的頻度較高，通過(guò)統(tǒng)計(jì)該社會(huì)團(tuán)體兩兩之間的通信強(qiáng)度發(fā)現(xiàn)該領(lǐng)導(dǎo)者處于整個(gè)社會(huì)團(tuán)體的“核心”，這種核心地位可以體現(xiàn)該領(lǐng)導(dǎo)者的“領(lǐng)導(dǎo)角色”。此外，還可以發(fā)現(xiàn)和統(tǒng)計(jì)其他角色，并分析這些角色之間關(guān)系的強(qiáng)度，如新浪微博中微博賬號(hào)之間的“粉絲”關(guān)系和相關(guān)“意見(jiàn)領(lǐng)袖”角色的發(fā)現(xiàn)和識(shí)別。

(4)演化：在現(xiàn)實(shí)網(wǎng)絡(luò)當(dāng)中，有些網(wǎng)絡(luò)是相對(duì)靜態(tài)的，如蛋白質(zhì)網(wǎng)絡(luò)、Internet的物理層網(wǎng)絡(luò)。而對(duì)大多數(shù)網(wǎng)絡(luò)來(lái)說(shuō)，其拓?fù)浣Y(jié)構(gòu)[8-10]會(huì)隨著時(shí)間而發(fā)生明顯的變化，如每個(gè)人所處的朋友圈在不同時(shí)期會(huì)有所不同。而當(dāng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，網(wǎng)絡(luò)中的點(diǎn)、關(guān)系和角色都有可能發(fā)生變化，變化的過(guò)程稱之為演化。以往的研究方法主要從整個(gè)網(wǎng)絡(luò)或某個(gè)特定時(shí)間快照出發(fā)，關(guān)注網(wǎng)絡(luò)全局特征在不同時(shí)間點(diǎn)上的變化，近年來(lái)，許多基于網(wǎng)絡(luò)演化的分析方法被應(yīng)用于各種社會(huì)關(guān)系網(wǎng)絡(luò)當(dāng)中[11-13]。這些方法中，利用圖來(lái)描述某一特定時(shí)間(如一天或一個(gè)月等)的網(wǎng)絡(luò)快照，基于這些圖序列，社會(huì)關(guān)系網(wǎng)絡(luò)的動(dòng)態(tài)特性就能夠被刻畫(huà)出來(lái)[14-15]，如圖1所示。

圖1　社會(huì)關(guān)系網(wǎng)絡(luò)組成要素

4社會(huì)關(guān)系網(wǎng)絡(luò)分析統(tǒng)計(jì)特性指標(biāo)

社會(huì)關(guān)系網(wǎng)絡(luò)分析中的統(tǒng)計(jì)特性指標(biāo)是針對(duì)具體社會(huì)關(guān)系網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析和統(tǒng)計(jì)的重要統(tǒng)計(jì)維度，結(jié)合近年來(lái)相關(guān)研究中涉及到的社會(huì)關(guān)系網(wǎng)絡(luò)的統(tǒng)計(jì)特性指標(biāo)，可大致分為宏觀性指標(biāo)和微觀性指標(biāo)兩大類。

(1)宏觀性指標(biāo)。宏觀性指標(biāo)側(cè)重于從社會(huì)關(guān)系網(wǎng)絡(luò)的整體角度去度量某個(gè)網(wǎng)絡(luò)的性質(zhì)和特征，這些指標(biāo)[16-21]主要包括網(wǎng)絡(luò)度分布指數(shù)、平均路徑長(zhǎng)度、反向平均路徑長(zhǎng)度、圖聚類系數(shù)、最大連通子圖大小、網(wǎng)絡(luò)Q值、結(jié)構(gòu)模塊性、網(wǎng)絡(luò)結(jié)構(gòu)熵、網(wǎng)絡(luò)容量等。

(2)微觀性指標(biāo)。微觀性指標(biāo)側(cè)重于從網(wǎng)絡(luò)的局部刻畫(huà)社會(huì)關(guān)系網(wǎng)絡(luò)的相關(guān)統(tǒng)計(jì)特性，主要分為4大類：點(diǎn)、邊、模體[22]以及社團(tuán)。各分類包括的統(tǒng)計(jì)特性指標(biāo)[23-27]如下：

點(diǎn)：點(diǎn)-度、點(diǎn)-強(qiáng)度、點(diǎn)-介數(shù)、點(diǎn)-聚類系數(shù)、點(diǎn)-中介中心性、點(diǎn)-度中心性、點(diǎn)-接近中心性等。

邊：邊-方向、邊-權(quán)、邊-介數(shù)等。

模體：Z-score(表示每個(gè)子圖的統(tǒng)計(jì)重要作用)、重要性剖面(significance profile)等。

社團(tuán)：社團(tuán)統(tǒng)計(jì)指標(biāo)又分為3類，即社團(tuán)基本統(tǒng)計(jì)指標(biāo)、單條件指標(biāo)和多條件指標(biāo)?；窘y(tǒng)計(jì)指標(biāo)包括社團(tuán)節(jié)點(diǎn)個(gè)數(shù)、社團(tuán)內(nèi)邊數(shù)等；單條件統(tǒng)計(jì)指標(biāo)由社團(tuán)基本統(tǒng)計(jì)指標(biāo)中的一項(xiàng)復(fù)合而成，主要有模塊度(社團(tuán)內(nèi)部模塊度)、模塊度比例、社團(tuán)內(nèi)點(diǎn)的度和、社團(tuán)邊界邊數(shù)等。多條件統(tǒng)計(jì)指標(biāo)由社團(tuán)基本統(tǒng)計(jì)指標(biāo)的多項(xiàng)復(fù)合而成，主要有導(dǎo)電率、擴(kuò)展率、內(nèi)部邊密度、截邊率、規(guī)范截邊率、MAX-ODF、Average-ODF、Flake-ODF等。

5社會(huì)關(guān)系網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分算法

研究人員發(fā)現(xiàn)許多實(shí)際的社會(huì)關(guān)系網(wǎng)絡(luò)是由若干個(gè)局部密集的“社團(tuán)”(社團(tuán)也被稱作虛擬社區(qū)、虛擬社團(tuán)等)所構(gòu)成的。每個(gè)社團(tuán)內(nèi)部的結(jié)點(diǎn)之間的連接相對(duì)緊密,社團(tuán)之間的連接相對(duì)來(lái)說(shuō)比較稀疏。這些社團(tuán)結(jié)構(gòu)代表了網(wǎng)絡(luò)中具有相同興趣偏好的團(tuán)體或聯(lián)系緊密的結(jié)構(gòu)，例如科學(xué)研究中的某一活躍領(lǐng)域和分支；萬(wàn)維網(wǎng)中主題相近的一組網(wǎng)頁(yè)；對(duì)某一類話題比較感興趣的微博用戶賬號(hào)、Twitter用戶賬號(hào)等。由于社會(huì)關(guān)系網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)和網(wǎng)絡(luò)功能有著緊密的關(guān)系，例如魯棒性、高傳播速度等，因此發(fā)現(xiàn)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是揭示網(wǎng)絡(luò)結(jié)構(gòu)和功能之間關(guān)系的重要基礎(chǔ)。

目前已有的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法旨在揭示出網(wǎng)絡(luò)中真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)，已被廣泛應(yīng)用于恐怖組織識(shí)別、組織結(jié)構(gòu)管理等具體的社會(huì)關(guān)系網(wǎng)絡(luò)分析[28-29]，以及Web社區(qū)挖掘和基于主題詞的Web文檔聚類[30-32]和搜索引擎[33-35]等眾多領(lǐng)域。社會(huì)關(guān)系網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的劃分算法大致分為以下3類：

(1)基于優(yōu)化的劃分方法?；趦?yōu)化的劃分方法主要分為譜方法[36]和局部搜索方法，其中譜方法N-Cut(normal cut)[40]和A-Cut(average cut)具有嚴(yán)密的數(shù)學(xué)理論,但是針對(duì)網(wǎng)絡(luò)的社團(tuán)劃分,譜方法不具備自動(dòng)識(shí)別網(wǎng)絡(luò)社團(tuán)總數(shù)的能力，而現(xiàn)實(shí)中的網(wǎng)絡(luò)往往包含多個(gè)網(wǎng)絡(luò)社團(tuán),譜方法的遞歸二分策略不能保證得到的網(wǎng)絡(luò)劃分是最優(yōu)的多網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。局部搜索方法部分主要基于目標(biāo)函數(shù)、候選解的搜索策略和最優(yōu)解的搜索策略，通過(guò)判斷目標(biāo)函數(shù)的某些局部最優(yōu)值來(lái)選取相應(yīng)的搜索策略。有代表性的局部搜索算法有Kernighan-Lin算法(簡(jiǎn)稱KL算法)[37]、FastGN算法[38]和Guimera-Amaral算法(簡(jiǎn)稱GA算法)[39]。KL算法需要先驗(yàn)知識(shí)(如社團(tuán)的個(gè)數(shù)或社團(tuán)的平均規(guī)模)，并且該算法對(duì)初始解異常敏感，不好的初始解將導(dǎo)致緩慢的收斂速度和較差的最終解。FastGN算法在社團(tuán)規(guī)模較大時(shí)準(zhǔn)確度不高，而GA算法時(shí)間復(fù)雜度太高，需要的計(jì)算時(shí)間較長(zhǎng)。

(2)啟發(fā)式劃分方法。典型的啟發(fā)式劃分算法有MFC(maximum flow community)算法、HITS(hyperlink induced topic search)算法[40]、GN算法、CPM(clique percolation method)算法和FEC(finding and extracting communities)算法[41]等，這類算法的共同特點(diǎn)是:基于某些直觀的假設(shè)來(lái)設(shè)計(jì)啟發(fā)式算法,對(duì)于大部分網(wǎng)絡(luò),其能夠快速地找到最優(yōu)解或者近似最優(yōu)解,但無(wú)法從理論上嚴(yán)格保證其對(duì)任何輸入網(wǎng)絡(luò)都能找到令人滿意的解。

(3)其他劃分方法。比較著名的有基于節(jié)點(diǎn)間相似度的算法，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)定義,如基于結(jié)構(gòu)全等的相關(guān)系數(shù)(correlation coefficient)算法[42]、基于隨機(jī)游走的相似度算法[43]和節(jié)點(diǎn)聚類中心度(clustering centrality)算法[44]等。

基于以上對(duì)社團(tuán)劃分方法的分類，可以得到基于優(yōu)化的劃分方法和啟發(fā)式劃分方法都存在一些各自的缺陷,比如基于優(yōu)化的方法計(jì)算時(shí)間比較長(zhǎng)，復(fù)雜度比較高，而啟發(fā)式劃分方法難以從理論上保證對(duì)輸入的任何網(wǎng)絡(luò)都有較滿意的解。

6研究展望

當(dāng)前在上述幾個(gè)核心問(wèn)題上的研究工作都面臨著社會(huì)關(guān)系網(wǎng)絡(luò)的具體形態(tài)快速發(fā)展所帶來(lái)的新問(wèn)題，也意味著每個(gè)方向上都有不少的挑戰(zhàn)。面對(duì)快速發(fā)展的各種社會(huì)關(guān)系網(wǎng)絡(luò)具體形態(tài)，筆者認(rèn)為以下幾個(gè)方面的研究將是未來(lái)社會(huì)關(guān)系網(wǎng)絡(luò)的研究核心。

(1)新生形態(tài)社會(huì)關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)特性研究。隨著各種新生形態(tài)的社會(huì)關(guān)系網(wǎng)絡(luò)承載形式的快速發(fā)展，如開(kāi)心網(wǎng)、新浪微博、Twitter、微信、騰訊QQ群等，深刻反映在線社會(huì)關(guān)系的社交網(wǎng)絡(luò)等產(chǎn)品和服務(wù)快速進(jìn)入人們的視野和生活，但是這些新生態(tài)社交網(wǎng)絡(luò)產(chǎn)品所反映出社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)特性又各有區(qū)別。因此，如何針對(duì)快速發(fā)展的新生形態(tài)社會(huì)關(guān)系網(wǎng)絡(luò)產(chǎn)品，構(gòu)建合適、準(zhǔn)確的網(wǎng)絡(luò)模型來(lái)統(tǒng)計(jì)和模擬其性能，并對(duì)其結(jié)構(gòu)特性進(jìn)行精準(zhǔn)的研究，準(zhǔn)確評(píng)估個(gè)體的影響力，制定合理的管理策略，是非常值得研究的科學(xué)問(wèn)題。

(2)多語(yǔ)言、復(fù)雜情感環(huán)境下社會(huì)關(guān)系網(wǎng)絡(luò)中信息語(yǔ)義、傾向性的多維判別。當(dāng)今互聯(lián)網(wǎng)上承載的社會(huì)關(guān)系網(wǎng)絡(luò)的相關(guān)應(yīng)用，早已跨越了國(guó)界、種族和語(yǔ)言的界限，同時(shí)隨著后Web 2.0時(shí)代的來(lái)臨，用戶在網(wǎng)絡(luò)上所表達(dá)的語(yǔ)義、情感也是逐漸傾向于褒義貶義混用、褒義貶義替換使用、多語(yǔ)言雜糅和多個(gè)情感、情緒的混合，這就給抓取互聯(lián)網(wǎng)信息后用戶信息的語(yǔ)義判別、情感傾向性判別增加了難度和噪聲。因此，如何在全球化背景下快速、準(zhǔn)確地判斷用戶語(yǔ)義信息中所表達(dá)的真實(shí)目的和相關(guān)言論，對(duì)于智能化判別技術(shù)而言，存在巨大的挑戰(zhàn)。

(3)社會(huì)關(guān)系網(wǎng)絡(luò)中信息產(chǎn)生、傳播過(guò)程的個(gè)體、群體心理互動(dòng)規(guī)律研究。社會(huì)關(guān)系網(wǎng)絡(luò)中的信息傳播過(guò)程涉及傳播個(gè)體、群體的心理互動(dòng)規(guī)律、信息傳播模式、個(gè)體群體觀點(diǎn)博弈等多個(gè)復(fù)雜過(guò)程，涉及到心理學(xué)、計(jì)算機(jī)以及管理學(xué)等多個(gè)學(xué)科，信息在社會(huì)關(guān)系網(wǎng)絡(luò)中的傳播(特別在非常規(guī)突發(fā)事件中)具有傳播方向、傳播內(nèi)容、傳播變異的多個(gè)不確定性，因此如何將機(jī)器學(xué)習(xí)、人工智能等技術(shù)與傳統(tǒng)的心理學(xué)、管理學(xué)理論相結(jié)合，構(gòu)建社會(huì)關(guān)系網(wǎng)絡(luò)中個(gè)體、群體在信息傳播過(guò)程中心理、行為等諸多要素的互動(dòng)規(guī)律，是當(dāng)前很多學(xué)者重點(diǎn)關(guān)注的熱點(diǎn)研究問(wèn)題。

7結(jié)論

隨著全球信息化、工業(yè)化進(jìn)程的加速和互聯(lián)網(wǎng)的快速發(fā)展，以在線社會(huì)關(guān)系網(wǎng)絡(luò)為代表的社交網(wǎng)絡(luò)的相關(guān)應(yīng)用正在迅速而深刻地改變著人們的生活，筆者從社會(huì)關(guān)系網(wǎng)絡(luò)的基本概念、社會(huì)關(guān)系網(wǎng)絡(luò)的分類、組成要素模型、分析統(tǒng)計(jì)特性指標(biāo)、社團(tuán)結(jié)構(gòu)劃分算法、個(gè)體與群體互動(dòng)規(guī)律等5個(gè)方面展開(kāi)討論，詳細(xì)研究和分析了當(dāng)前在社會(huì)關(guān)系網(wǎng)絡(luò)方面已有的最近研究成果，以及未來(lái)發(fā)展趨勢(shì)和主要研究方向?？傊鐣?huì)關(guān)系網(wǎng)絡(luò)方面的研究處于快速發(fā)展和變化當(dāng)中，尚有諸多問(wèn)題亟待解決。

參考文獻(xiàn)：

[1]王元卓,靳小龍,程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：研究與展望[J].計(jì)算機(jī)學(xué)報(bào),2013,36(6):1125-1138.

[2]劉軍.整體網(wǎng)分析講義:UCINET軟件實(shí)用指南[M].上海:上海人民出版社,2009:32-98.

[3]羅家德.社會(huì)網(wǎng)絡(luò)分析講義[M].北京:社會(huì)科學(xué)文獻(xiàn)出版社,2010:101-123.

[4]PALLA G,BARABASI A L,VICSEK T.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[5]KUMAR R,NOVAK J,TOMKINS A.Structure and evolution of online social networks[C]∥Link Mining: Models,Algorithms and Applications.New York :Springer New York,2010:337-357.

[6]BARABASI A L,BONABEAU E.Scale-free networks [J].Scientific American,2003(288):60-69.

[7]GIRVAN M,NEWMAN E J.Community structure in social and biological networks [J].PNAS,2002,99(12):7821-7826.

[8]ONNELA J P ,SARAMAKI J,HYVONEN J,et al.Structure and tie strengths in mobile communication networks[J].PNAS,2007,104(18):7332-7336.

[9]NEWMA M E J.Coauthorship networks and patterns of scientific collaboration [J].PNAS,2004,101(s1):5200-5205.

[10]HOPCROFT J,KHAN O,KULIS B,et al.Tracking evolving communities in large linked networks [J].PNAS,2004,101(s1)：5249-5253.

[11]SUN J M,FALOUTSOS C,PAPADIMITRIOU S,et al.GraphScope: parameter-free mining of large time-evolving graphs[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2007:687-696.

[12]KUMAR R,NOVAK J,TOMKINS A.Structure and evolution of online social networks[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2006:611-617.

[13]ASUR S,PARTHASARATHY S.An event-based framework for characterizing the Evolutionary behavior of interaction graphs [C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2007:913-921.

[14]BERGE W,TANYA Y,SAIA J.A framework for analysis of dynamic social networks[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]:ACM,2006:523-528.

[15]LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graphs over time: densification laws,shrinking diameters and possible explanations[C]∥Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.[S.l.]:ACM， 2005:177-187.

[16]REKA A,HAWOONG J.Error and attack tolerance of complex networks [J].Nature,2000(406):378-382.

[17]BOGUNA M,PASTOR-SATORRAS R.Epidemic spreading in correlated complex networks [J].Physical Review E,2002,66(7):7104-7106.

[18]ALBERT R,BARABASI A L.Statistical mechanics of complex networks[J].Review of Modern Physics,2001,74(1):47-97.

[19]NEWMAN M E J.Finding community structure in networks using the Eigenvectors of matrices [J].Physical Review E,2006,74(3):6104-6107.

[20]SOLE R V,VALVERDE S.Information theory of complex networks: on evolution and architectural constraints[J].Lecture Notes in Physics,2004(650):189-210.

[21]PROKOPENKO M,WANG P.Self-organizing hierarchies in sensor and communication networks[J].Artificial Life,2005(11):407-426.

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

[23]DOROGOVTSEV S N ,MENDES J F F.The shortest path to complex networks [J].Am J Med Genet,2004(71):47-53.

[24]NEWMA M E J.Who is the best connected scientist: a study of scientific coauthorship networks [J].Lecture Notes in Physics,2004(650):337-370.

[25]FREEMAN L C.A set of measures of centrality based on betweenness [J].Sociometry,1977(40):35-41.

[26]CHRISTINE K,MARTIN B.Identification of influencers-measuring influence in customer networks [J].Decision Support Systems Archive,2008(10):233-253.

[27]LESKOVEC J,KEVIN J.Empirical comparison of algorithms for network community detection[C]∥Proceedings of the 19th International Conference on World Wide Web.[S.l.]:[s.n.],2010:631-640.

[28]PALLA G,DERENYI I.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[29]TYLER J R,WILKINSON D M.Email as spectroscopy: automated discovery of community structure within organizations[C]∥Proc of the 1st Int’l Conf on Communities and Technologies.Dordrecht: Kluwer Academic Publishers,2003:81-96.

[30]FLAKE G W,LAWEWNCE S,GILES C L,et al.Self-organization and identification of web communities [J].IEEE Computer,2002,35(3):66-71.

[31]LI X,LIU B,YU P S.Discovering overlapping communities of named entities[C]∥Proc of the 10th European Conf on Principles and Practice of Knowledge Discovery in Databases.Berlin: Springer-Verlag,2006:593-600.

[32]INO H,KUDO M.Partitioning of web graphs by community topology[C]∥Proc of the 14th Int’l Conf on World Wide Web.New York: ACM,2005:661-669.

[33]KLEINBERG J M.Authoritative sources in a hyperlinked environment [J].Journal of the ACM,1999,46(5):604-632.

[34]ALMEDIA R B,ALMEDIA V A F.A community-aware search Engine[C]∥Proc of the 13th Int’l Conf on World Wide Web.New York: ACM,2004:413-421.

[35]SIDIROPULOS A,PALLAIS G.Prefetching in content distribution networks via web communities identification and outsourcing[J].World Wide Web,2008,11(1):39-70.

[36]SHIGA M,TAKIGAWA I.A spectral clustering approach to optimally combining numerical Vectors with a Modular Network[C]∥Proc of the 13th ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining.New York: ACM,2007:647-656.

[37]NEWMAN M E J.Detecting community structure in networks [J].European Physical Journal(B),2004,38(2):321-330.

[38]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):6133-6136.

[39]GUIMERA R,AMARAL L A N.Functional cartography of complex metabolic networks [J].Nature,2005,433(7028):895-900.

[40]KLEINBERG J M.Authoritative sources in a hyperlinked environment [J].Journal of the ACM,1999,46(5):604-632.

[41]YANG B,CHEUNG W K.Community mining from signed social networks [J].IEEE Trans on Knowledge and Data Engineering,2007,19(10):1333-1348.

[42]WASSEMAN S,FAUST K.Social network analysis [M].Cambridge: Cambridge University Press,1994:103-189.

[43]PONS P,LATAPY M.Computing communities in large networks using random walks [J].Lecture Notes in Computer Science,2005(3733):284-293.

[44]FORTUNATOS,LATORA V,MARCHIORI M.Method to find community structures based on information centrality [J].Physical Review E,2004,70(5):6104-6109.

DENG Xiaolong:Assistant Professor；Key Lab of Trustworthy Distributed Computing and Service of Education Ministry ,Beijing University of Post and Telecommunication,Beijing 100876,China.

[編輯：王志全]

文章編號(hào)：2095-3852(2016)01-0008-06

文獻(xiàn)標(biāo)志碼:A

收稿日期：2015-10-26.

作者簡(jiǎn)介：鄧小龍(1977-),男,湖北沙市人,北京郵電大學(xué)可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室講師；博士.

基金項(xiàng)目：十二五國(guó)家科技支撐計(jì)劃資金資助項(xiàng)目 (2013BAH43F01) ；國(guó)家自然科學(xué)基金重大研究計(jì)劃資金資助項(xiàng)目 (91124002).

中圖分類號(hào)：C912.3;X915.2

DOI：10.3963/j.issn.2095-3852.2016.01.002

Social Network Analysis Basic Theory:Present and Future

DENG Xiaolong,LI Yuxiao,ZENG Jie

Abstract：With very fast developing speed of online social network users and their influence to our daily life,it is urgent for researchers to explore the essential scientific problem,investigate the disciplinary issues and common laws of social network,study the fundamental theory and basic approach to qualitatively or quantitatively researching on social network.And in recent years,researchers always focus on three components of relation structure,network group and network information to explore the essence of social network.To dealing the three essential components above,this paper analyzes and summary the related work of six aspects of social network such as basic concept,classification,components,statistical indicators,community detection algorithm in social network.It also looks ahead to the development trends of social network such as structure statistic analysis of new generation in social network,information semantic recognition and sentiment judgment in multilingual and complex sentiments environment,psychological interaction disciplines in information spreading process and so on.

Key words：social network; classification; components; statistical indicators; community detection; individuals and group interaction