具有社團(tuán)特征的社交網(wǎng)絡(luò)建模方法*

莫 嫻，錢京梅，吳 茜

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展，人們的生活更加便捷，互聯(lián)網(wǎng)的在線社交網(wǎng)絡(luò)與人們的生活越來越緊密，F(xiàn)acebook、Twitter、微博等社交媒體極大地豐富了人們的生活，其中微博在國內(nèi)應(yīng)用最為廣泛。

微博內(nèi)容豐富、新穎、及時(shí)，用戶能夠隨時(shí)隨地獲取大量信息。同時(shí)，微博具有低門檻性，只要成為微博用戶，就能發(fā)表自己的意見，容易獲取別人的認(rèn)同，具有較強(qiáng)的參與性。微博用戶數(shù)量龐大，用戶間的關(guān)系復(fù)雜，可以用有向圖G=(V,E)表示，其中V表示用戶節(jié)點(diǎn)集合，E表示用戶間的連接關(guān)系集合。用戶通過關(guān)注與被關(guān)注的方式，實(shí)現(xiàn)用戶之間的信息交互,在社交網(wǎng)絡(luò)拓?fù)渲?，用一條邊表示。同時(shí)，微博中，信息流具有方向性。例如，節(jié)點(diǎn)A關(guān)注節(jié)點(diǎn)B，A就成為B的粉絲，用A→B表示，而信息卻是由B傳向A；如果節(jié)點(diǎn)A與節(jié)點(diǎn)B相互關(guān)注，則用雙向邊A?B表示，信息可雙向傳遞。整個(gè)微博可以用有向網(wǎng)絡(luò)進(jìn)行描述，如圖1所示，網(wǎng)絡(luò)拓?fù)淠軌蚯逦砻饔脩糁g的連接關(guān)系、信息流向等信息。

圖1 微博網(wǎng)絡(luò)拓?fù)?/p>

通過連接關(guān)系的特點(diǎn)，可以將微博用戶大致分為普通節(jié)點(diǎn)和大V節(jié)點(diǎn)。大V節(jié)點(diǎn)關(guān)注少量節(jié)點(diǎn)，但具有大量粉絲，具有高入度、低出度的拓?fù)涮匦裕黄胀ü?jié)點(diǎn)的粉絲節(jié)點(diǎn)少，但他們通常會關(guān)注較多節(jié)點(diǎn)，具有低入度、高出度的拓?fù)涮匦裕煌瑫r(shí)存在少量節(jié)點(diǎn)，即沒有關(guān)注其他節(jié)點(diǎn)，其他節(jié)點(diǎn)也不關(guān)注他，成為孤立節(jié)點(diǎn)，這種節(jié)點(diǎn)對信息的傳遞沒有影響，在網(wǎng)絡(luò)拓?fù)渲胁挥杳枋觥?/p>

信息是如何在微博中傳播的呢？用戶發(fā)布微博，他的粉絲能夠看到該信息，粉絲可以通過轉(zhuǎn)發(fā)、評論、點(diǎn)贊等行為表達(dá)自己的意見；通過轉(zhuǎn)發(fā)該微博，可以使粉絲的粉絲節(jié)點(diǎn)獲取該信息，從而引起信息的進(jìn)一步擴(kuò)散；評論數(shù)、點(diǎn)贊數(shù)、轉(zhuǎn)發(fā)數(shù)較多的話題，更能吸引粉絲評論、點(diǎn)贊及轉(zhuǎn)發(fā)，通過這樣的方式信息能夠迅速在網(wǎng)絡(luò)中彌散，如圖2所示。熱門話題的發(fā)帖數(shù)、轉(zhuǎn)發(fā)數(shù)、評論數(shù)、點(diǎn)贊數(shù)等都較高，它的影響更廣泛。

圖2 微博信息傳播

社交網(wǎng)絡(luò)中有些個(gè)體之間關(guān)系密切，有些關(guān)系生疏，在圍繞某一個(gè)焦點(diǎn)時(shí)又形成了聯(lián)系更為密切的社區(qū)形式，可以看作社交網(wǎng)絡(luò)中的虛擬社區(qū)結(jié)構(gòu)，稱為社團(tuán)。虛擬社區(qū)結(jié)構(gòu)是在線社交網(wǎng)絡(luò)的一種典型拓?fù)浣Y(jié)構(gòu)特征，反映了網(wǎng)絡(luò)中個(gè)體行為的局部聚集特征[1]。通過統(tǒng)計(jì)分析可知，微博網(wǎng)絡(luò)具有社團(tuán)特征，有相同興趣、愛好的用戶更容易形成一個(gè)社團(tuán)。從網(wǎng)絡(luò)拓?fù)渖嫌^察，社團(tuán)具有社團(tuán)內(nèi)節(jié)點(diǎn)相互連接密集而社團(tuán)間節(jié)點(diǎn)相互連接稀疏的特點(diǎn)，如圖3所示。在微博中，部分用戶行為具有相似性，如對某一話題感興趣的用戶會相互關(guān)注，且會關(guān)注該類話題的大V節(jié)點(diǎn)，對這一話題的參與度也較高，表現(xiàn)行為就是轉(zhuǎn)發(fā)該類話題的微博、點(diǎn)贊頻度較高、會在微博發(fā)表自己的意見等，而對其他話題的微博反應(yīng)平淡，也許會有相關(guān)動作，但頻度很低。

圖3 社團(tuán)示意

1 相關(guān)研究

目前，已有大量學(xué)者對微博展開了研究，同時(shí)對微博網(wǎng)絡(luò)進(jìn)行了建模。常見的建模方式有兩類，一類是通過真實(shí)數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)拓?fù)?，一類是通過相關(guān)微博特征參數(shù)構(gòu)建網(wǎng)絡(luò)拓?fù)洹?/p>

1.1 通過真實(shí)數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)拓?fù)?/h3>

該類建模方式主要通過網(wǎng)絡(luò)爬蟲的方法獲取真實(shí)數(shù)據(jù)，從而分析構(gòu)建網(wǎng)絡(luò)拓?fù)?。通常，選取已經(jīng)發(fā)生的熱門事件為中心，爬取微博上關(guān)于該事件的發(fā)帖、評論、點(diǎn)贊、轉(zhuǎn)發(fā)等相關(guān)信息，采用大數(shù)據(jù)分析的手段，形成某一話題的傳播途徑，構(gòu)建微博網(wǎng)絡(luò)拓?fù)洹＿@樣構(gòu)建的網(wǎng)絡(luò)拓?fù)渑c真實(shí)世界一致，完整并直觀展現(xiàn)了微博網(wǎng)絡(luò)的結(jié)構(gòu)特征和信息傳播特性，能夠充分分析話題在網(wǎng)絡(luò)中的擴(kuò)散程度和對人群的影響力。

例如，在《新浪微博的大規(guī)模信息傳播規(guī)律研究》一文中，選取2012年4月到2012年9月期間部分熱門話題的微博數(shù)據(jù)，得出了波紋式模型、蒲公英式模型、菌落式模型、煙花式模型、蜂巢式模型、雙子星式模型和隨機(jī)引爆式模型等幾類傳播模型，

并分別對7種傳播模型進(jìn)行了分析[2]。

由真實(shí)數(shù)據(jù)建立的網(wǎng)絡(luò)拓?fù)涿枋龅氖窃谀骋惶囟〞r(shí)期、針對特定話題的拓?fù)淝闆r，當(dāng)時(shí)間、事件發(fā)生改變時(shí)，網(wǎng)絡(luò)拓?fù)潆S之改變，不會具有相似性，體現(xiàn)了網(wǎng)絡(luò)演化的特點(diǎn)。采取這種方式構(gòu)建社交網(wǎng)絡(luò)拓?fù)?，通常?yīng)用于輿情分析、評估、模型驗(yàn)證等方面。

1.2 通過特征參數(shù)構(gòu)建網(wǎng)絡(luò)拓?fù)?/h3>

該類方式是通過已有的研究成果，獲取微博網(wǎng)絡(luò)的特征，并默認(rèn)整個(gè)微博網(wǎng)絡(luò)滿足這些特征，從而構(gòu)建用戶要求規(guī)模的微博網(wǎng)絡(luò)。該類方式主要研究社交網(wǎng)絡(luò)傳播過程的基礎(chǔ)拓?fù)錁?gòu)建。

在《微博網(wǎng)絡(luò)傳播行為中的關(guān)鍵問題研究》一文中，以新浪微博為研究對象，提出了一種微博網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法。通過爬取一定數(shù)量的微博數(shù)據(jù)，分析新浪微博的社團(tuán)特征和用戶連接特征，并將此作為構(gòu)建微博社交網(wǎng)絡(luò)的特征參數(shù)，提出一種“生成具有不同模塊度和雙向邊比例的模擬網(wǎng)絡(luò)”算法[3]。

在《NCSS：一種快速有效的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法》一文中，根據(jù)復(fù)雜網(wǎng)絡(luò)的社團(tuán)特性，提出一種關(guān)于復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法。該算法采用社團(tuán)擴(kuò)張的方式逐步增加用戶，最終形成一定規(guī)模的具有社團(tuán)特征的復(fù)雜網(wǎng)絡(luò)[4]。

在《微博社交網(wǎng)絡(luò)模型的建立及其性質(zhì)研究》一文中，提出了網(wǎng)絡(luò)初始默認(rèn)社團(tuán)、社團(tuán)開放度的屬性及節(jié)點(diǎn)Interests等概念，并以此約束節(jié)點(diǎn)間差異的連接行為形成社團(tuán)結(jié)構(gòu)，提出了COMW模型和IBMW模型[5]。

2 具有社團(tuán)特征的社交網(wǎng)絡(luò)模型

為了研究社交網(wǎng)絡(luò)對信息傳播的影響，探索社會網(wǎng)絡(luò)信息傳播規(guī)律，本文側(cè)重于構(gòu)建大規(guī)模社交網(wǎng)絡(luò)模型，盡可能真實(shí)模擬微博用戶數(shù)量龐大、用戶關(guān)系復(fù)雜的實(shí)際情況，以期為后續(xù)研究提供一個(gè)更可靠的基礎(chǔ)環(huán)境。這里，提出一種具有社團(tuán)特征的社交網(wǎng)絡(luò)模型，通過已有文獻(xiàn)研究的微博網(wǎng)絡(luò)的特征參數(shù)，構(gòu)建一個(gè)大規(guī)模的具有微博特征的社交網(wǎng)絡(luò)。該模型能夠描述微博社交網(wǎng)絡(luò)的社團(tuán)特性，呈現(xiàn)出社團(tuán)間聯(lián)系較稀疏、社團(tuán)內(nèi)節(jié)點(diǎn)聯(lián)系緊密的特征，并且可以區(qū)分大V節(jié)點(diǎn)和普通節(jié)點(diǎn)。

本模型的基本思路是根據(jù)需求劃分社團(tuán)，逐一對每個(gè)社團(tuán)進(jìn)行建模，最后按照一定規(guī)則將社團(tuán)連接起來，從而完成整個(gè)微博社交網(wǎng)絡(luò)的建模，流程如圖4所示。

圖4 社交網(wǎng)絡(luò)構(gòu)建過程

2.1 劃分社團(tuán)

構(gòu)建社交網(wǎng)絡(luò)首先需要確定模擬網(wǎng)絡(luò)的規(guī)模和社團(tuán)數(shù)量，以此為依據(jù)劃分社團(tuán)。需要確定的參數(shù)為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)、社團(tuán)規(guī)模特征、社團(tuán)個(gè)數(shù)、用戶節(jié)點(diǎn)數(shù)、大V節(jié)點(diǎn)數(shù)。劃分社團(tuán)時(shí)，需滿足社團(tuán)大小（即社團(tuán)內(nèi)節(jié)點(diǎn)的數(shù)量）服從冪指數(shù)為2的冪律分布規(guī)律[6-7]。

2.2 標(biāo)題構(gòu)建社團(tuán)

這里已經(jīng)明確社團(tuán)的規(guī)模N及社團(tuán)內(nèi)的大V節(jié)點(diǎn)數(shù)v，構(gòu)建社團(tuán)的流程如圖5所示。

圖5 社團(tuán)的構(gòu)建過程

實(shí)現(xiàn)過程如下：

（1）按照構(gòu)造小世界網(wǎng)絡(luò)的算法構(gòu)建N-v個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)洹Ｔ摬襟E生成的邊為源節(jié)點(diǎn)關(guān)注目的節(jié)點(diǎn)的單向邊。記錄節(jié)點(diǎn)之間邊的情況，形成有向邊集合。

（2）根據(jù)網(wǎng)絡(luò)密度ρ計(jì)算網(wǎng)絡(luò)中邊的總數(shù)，由雙邊概率q計(jì)算雙向邊的數(shù)量。網(wǎng)絡(luò)密度的定義為，其中X表示網(wǎng)絡(luò)中邊的總數(shù)，N表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。已有相關(guān)文獻(xiàn)對微博的網(wǎng)絡(luò)密度進(jìn)行了研究，規(guī)模在1 000～7 000個(gè)節(jié)點(diǎn)的社團(tuán)，網(wǎng)絡(luò)密度的范圍為0.000 4～0.052 2，平均值為0.007 7。雙邊概率是指節(jié)點(diǎn)間相互關(guān)注的情況，在微博中較少，q的取值范圍為0.2～0.25[2]。

（3）優(yōu)先選擇度數(shù)較高的節(jié)點(diǎn)，完成單向邊連接。依次遍歷節(jié)點(diǎn)，將其作為源節(jié)點(diǎn)。在最開始階段，節(jié)點(diǎn)的度基本一致，隨機(jī)選擇目的節(jié)點(diǎn)，完成單向邊連接。當(dāng)遍歷開始后，節(jié)點(diǎn)的度產(chǎn)生變化，此時(shí)優(yōu)先選擇度數(shù)較高的節(jié)點(diǎn)。這與微博用戶的實(shí)際行為一致，用戶總是更容易關(guān)注粉絲數(shù)量較多的用戶，這種現(xiàn)象稱為“馬太效應(yīng)”。社團(tuán)中的節(jié)點(diǎn)i與源節(jié)點(diǎn)的連接概率i∏滿足：

其中，ki表示節(jié)點(diǎn)i的度[8]。

（4）完成雙向邊連接，以概率q從有向邊集合中選出部分邊，將每條單向邊等價(jià)為兩條具有相反方向的有向邊，q為用戶對之間存在雙向邊的概率。

（5）生成大V節(jié)點(diǎn)，完成大V節(jié)點(diǎn)和普通節(jié)點(diǎn)的連接關(guān)系，以概率Pv選取普通節(jié)點(diǎn)和大V節(jié)點(diǎn)的單向連接（普通節(jié)點(diǎn)關(guān)注大V節(jié)點(diǎn)），以概率Pn選取大V節(jié)點(diǎn)和普通節(jié)點(diǎn)的單向連接（大V節(jié)點(diǎn)關(guān)注普通節(jié)點(diǎn)）。

2.3 社團(tuán)連接

經(jīng)過2.2節(jié)后，已存在多個(gè)獨(dú)立的社團(tuán)，需通過一定的規(guī)律將其連接起來，避免出現(xiàn)孤立社團(tuán)。社團(tuán)連接流程如圖6所示。

圖6 社團(tuán)連接過程

實(shí)現(xiàn)過程如下：

（1）根據(jù)模塊度Q計(jì)算社團(tuán)間連接邊的數(shù)量，由此確定需要連接的節(jié)點(diǎn)對數(shù)量。復(fù)雜網(wǎng)絡(luò)中提到了模塊度（Modularity）的概念，它可以衡量社團(tuán)劃分的質(zhì)量。當(dāng)模塊度Q的值在0.3與0.7時(shí)，表明網(wǎng)絡(luò)具有明顯的社團(tuán)特性。微博網(wǎng)絡(luò)的模塊度Q值基本穩(wěn)定在0.374左右。模塊度的計(jì)算公式為[9]：

其中vre∑表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的連邊中，包含在社團(tuán)v內(nèi)各節(jié)點(diǎn)的所有連邊的比例；av表示一邊與社團(tuán)v內(nèi)節(jié)點(diǎn)相連的邊所占的比例。

（2）選取節(jié)點(diǎn)，使節(jié)點(diǎn)位于不同的社團(tuán)，用有向邊相連，并保證節(jié)點(diǎn)之間都是單向連接，記錄這些有向邊形成有向邊集合。

（3）以概率q從有向邊集合中選出部分邊，將每條單向邊等價(jià)為兩條具有相反方向的有向邊，q即為用戶對之間存在雙向邊的概率。

（4）完成大V節(jié)點(diǎn)與其他社團(tuán)的大V節(jié)點(diǎn)、普通節(jié)點(diǎn)的連接。

（5）檢測網(wǎng)絡(luò)，若存在孤立社團(tuán)，將其大V節(jié)點(diǎn)與其他社團(tuán)的大V節(jié)點(diǎn)相連。

3 結(jié) 語

本文提出了具有社團(tuán)特性的社交網(wǎng)絡(luò)模型，借鑒小世界網(wǎng)絡(luò)模型和BA無標(biāo)度網(wǎng)絡(luò)模型進(jìn)行完善，以網(wǎng)絡(luò)密度和雙邊概率作為社團(tuán)構(gòu)建的關(guān)鍵參數(shù)，生成單獨(dú)的社團(tuán)網(wǎng)絡(luò)。由于在社團(tuán)中大V節(jié)點(diǎn)數(shù)量較少，其特征與普通節(jié)點(diǎn)不同，這里將大V節(jié)點(diǎn)與普通節(jié)點(diǎn)區(qū)分開，通過概率Pv、Pn調(diào)節(jié)大V節(jié)點(diǎn)的連接關(guān)系，最后將各個(gè)社團(tuán)連接起來，使之滿足模塊度要求，形成整個(gè)社交網(wǎng)絡(luò)。國際上關(guān)于社交網(wǎng)絡(luò)的研究仍處于初級階段，尚未提出完整的社交網(wǎng)絡(luò)分析的基礎(chǔ)理論和方法，值得進(jìn)一步進(jìn)行研究和突破[1]。

[1] 方濱興,賈焰,韓毅.社交網(wǎng)絡(luò)分析核心科學(xué)問題、研究現(xiàn)狀及未來展望[J].中國科學(xué)院院刊,2015(02):187-199.FANG Bin-xing,JIA Yan,HAN Yi.Social Network Analysis-Key Research Problems,Related Work,and Future Prospects[J].Bulletin of Chinese Academy of Sciences,2015(02):187-199.

[2] 易成岐,鮑媛媛,薛一波等.新浪微博的大規(guī)模信息傳播規(guī)律研究[J].計(jì)算機(jī)科學(xué)與探索,2013,7(06):551-561.YI Cheng-qi,BAO Yuan-yuan,XUE Yi-bo,et al.Research on Mechanism of Large-Scale Information Dissemination Based on Sina Weibo[J].Journal of Frontiers of Computer Science and Technology,2013,7(06):551-561.

[3] 熊小兵.微博網(wǎng)絡(luò)傳播行為中的關(guān)鍵問題研究[D].鄭州:解放軍信息工程大學(xué),2013.XIONG Xiao-bing.Research on Key Issues of Spreading Behavior in Microblogging Network[D].Zhengzhou:PLA Information Engineering University for the Degree of Doctor of Engineering,2013.

[4] 韓忠明,譚旭升,陳炎等.NCSS——一種快速有效的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法[J].中國科學(xué):信息科學(xué),2016,46(04):431-444.HAN Zhong-ming,TAN Xu-sheng,CHEN Yan,et al.NCSS:an Effective and Efficient Complex Network Community Detection Algorithm[J].Science China:Scientia Sinica Informationis,2016,46(04):431-444.

[5] 楊強(qiáng).微博社交網(wǎng)絡(luò)模型的建立及其性質(zhì)研究[D].北京:北京化工大學(xué),2015.YANG Qiang.Establishment and Study of the Properties of WEIBO Social Network Model[D].Beijing:Beijing University of Chemical Technology,2015.

[6] Danon L,Duch J,Diazguilera A.Comparing Community Structure Identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(09):09008.

[7] Radicchi F,Castellano C,Cecconi F.Defining and Identifying Communities in Networks[J].Proceedings of the National Academy of Sciences,2004,101(09):2658-2663.

[8] Bianconi G,Barabasi A L.Bose-Einstein Condensation in Complex Networks[J].Physical Review Letters,2001,86(24):5632-5635.

[9] Clauset A,Newman M E,Moore C.Finding Community Structure in Very Large Networks[J].Physical Review E,2004,70(06):066111.