王長(zhǎng)輝

(成都紡織高等?？茖W(xué)校)

0 引言

網(wǎng)絡(luò)論壇(BBS)由于具有及時(shí)性、交互性、開放性等特點(diǎn)，因而也是網(wǎng)絡(luò)輿論產(chǎn)生、形成和發(fā)展的主要場(chǎng)所，整個(gè)網(wǎng)絡(luò)論壇的參與者呈現(xiàn)一種特性— —社團(tuán)結(jié)構(gòu)，即整個(gè)網(wǎng)絡(luò)由若干個(gè)社團(tuán)構(gòu)成，每個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)之間的連接相對(duì)緊密，各社團(tuán)之間的連接相對(duì)稀疏.研究網(wǎng)絡(luò)論壇的社團(tuán)結(jié)構(gòu)，對(duì)了解BBS中網(wǎng)絡(luò)輿論的傳播特點(diǎn)具有現(xiàn)實(shí)意義.

網(wǎng)絡(luò)論壇中成員根據(jù)興趣或背景而形成真實(shí)的社會(huì)團(tuán)體，網(wǎng)絡(luò)中的這些社區(qū)有助于更加有效地理解其成員結(jié)構(gòu)和分析網(wǎng)絡(luò)輿論傳播特性.目前對(duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)研究主要有兩類主要的方法——社會(huì)學(xué)中的分級(jí)聚類和計(jì)算機(jī)科學(xué)中的圖形分割方法.分級(jí)聚類是探測(cè)網(wǎng)絡(luò)社團(tuán)的傳統(tǒng)方法，基于各個(gè)節(jié)點(diǎn)間連接的相似性或強(qiáng)度將網(wǎng)絡(luò)劃分成子群，并根據(jù)劃分時(shí)是往網(wǎng)絡(luò)中添加還是移除邊可分為凝聚算法和分裂算法，Girvan和Newman提出基于邊介數(shù)的分裂算法(簡(jiǎn)稱GN算法);Kemighan－Lin算法和譜平分法則是較為出名的圖形分割算法，其中Kernighan－Lin算法根據(jù)使社團(tuán)內(nèi)部及社團(tuán)間的邊最優(yōu)化的原則對(duì)原始的網(wǎng)絡(luò)進(jìn)行分類，譜平分法是根據(jù)網(wǎng)絡(luò)圖的Laplace矩陣進(jìn)行向特征向量空間的譜映射［1，6－8］.該文算法是譜平分法的一種改進(jìn)算法，將模塊度函數(shù)與聚類分析算法結(jié)合進(jìn)行社團(tuán)結(jié)構(gòu)探測(cè).

1 算法簡(jiǎn)介

網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)與數(shù)據(jù)的聚類分析有很多相似之處，聚類分析屬于無(wú)監(jiān)督的模式識(shí)別，其方法比社團(tuán)發(fā)現(xiàn)更豐富，把聚類分析方法應(yīng)用到BBS網(wǎng)民關(guān)系網(wǎng)絡(luò)中可發(fā)現(xiàn)網(wǎng)民構(gòu)成的社團(tuán)結(jié)構(gòu).應(yīng)用聚類分析方法來(lái)探測(cè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分為兩個(gè)步驟:第一步是將原問(wèn)題轉(zhuǎn)化為聚類問(wèn)題，即要把網(wǎng)絡(luò)中節(jié)點(diǎn)間的聯(lián)系在特征向量空間中表述出來(lái)，譜平分法可實(shí)現(xiàn)這一轉(zhuǎn)化;第二步對(duì)轉(zhuǎn)化后的數(shù)據(jù)進(jìn)行聚類并將聚類結(jié)果還原為相應(yīng)的社團(tuán)結(jié)構(gòu)，該文在聚類過(guò)程中結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)特征，用社團(tuán)結(jié)構(gòu)的模塊度來(lái)控制聚類過(guò)程，并使用模擬退火算法來(lái)進(jìn)行聚類.

1.1 BBS無(wú)向網(wǎng)絡(luò)的建立

該文對(duì)BBS中網(wǎng)民n1和n2間關(guān)系給出4種不同的度量方式:

(1)網(wǎng)頁(yè)同現(xiàn):記C1(n1，n2)為n1和n2同時(shí)出現(xiàn)的網(wǎng)頁(yè)個(gè)數(shù).

(2)同帖同現(xiàn):記C2(n1，n2)為n1和n2同時(shí)出現(xiàn)在一個(gè)帖子中的個(gè)數(shù).

(3)同句同現(xiàn):記C3(n1，n2)為n1和n2同時(shí)出現(xiàn)在一個(gè)句子中，且其間隔的字符數(shù)小于一個(gè)閾值(該文取20)的語(yǔ)句個(gè)數(shù).

(4)連接詞同現(xiàn):定義一組連接詞:{和，跟，與，同，and，或者，“頓號(hào)”}.記 C4(n1，n2)為 n1和n2由連接詞連接的次數(shù).

通過(guò)上述4種方法來(lái)定義任意兩個(gè)網(wǎng)民n1和n2間的相關(guān)度:

C(n1，n2)=，(其中 pi為權(quán)重系數(shù)，這里取(p1，p2，p3，p4)=

記Ci(nj)為nj在第i種度量方法中出現(xiàn)的次數(shù)定義一個(gè)閾值flag(這里取0.05)，若:

則記n1和n2有關(guān)系邊，且邊的權(quán)為相關(guān)度C(n1，n2)，遍歷所有2元人物對(duì)，可獲得BBS關(guān)系網(wǎng)絡(luò)的連接權(quán)矩陣W，從而建立論壇中的無(wú)向關(guān)系網(wǎng)絡(luò)，記此關(guān)系網(wǎng)絡(luò)為G(V，E，W).

1.2 模塊度函數(shù)的應(yīng)用

Newman等人引進(jìn)了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度［9－10］.對(duì)具有n個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)G(V，E，W)，其中V為節(jié)點(diǎn)集，E為邊集，W=(wij)m×n為權(quán)矩陣.對(duì)此網(wǎng)絡(luò)得出的某個(gè)k社團(tuán)劃分Pk，其對(duì)應(yīng)的模塊度定義為

其中，A(Vc，Vc)表示在社團(tuán)c中所有邊的權(quán)重和，A(Vc，V)表示所有與社團(tuán)c中的節(jié)點(diǎn)有連線的邊的權(quán)重和，A(V，V)表示整個(gè)網(wǎng)絡(luò)中邊的權(quán)重和.基于這樣的定義，當(dāng)網(wǎng)絡(luò)的k社團(tuán)結(jié)構(gòu)越明顯，則M(Pk)值越大，用M(Pk)作為社團(tuán)結(jié)構(gòu)有效度度量的標(biāo)準(zhǔn)［10］.該文中，模塊度是社團(tuán)結(jié)構(gòu)有效度量，作為優(yōu)化迭代的一個(gè)指標(biāo)應(yīng)用到聚類算法中，在搜尋最佳社團(tuán)數(shù)，設(shè)定聚類數(shù)條件下與目標(biāo)函數(shù)值結(jié)合作為迭代的終止條件，在算法中作為適應(yīng)度函數(shù)來(lái)控制算法的進(jìn)化過(guò)程.

1.3 模擬退火算法

模擬退火算法模擬熔融狀態(tài)下物體逐漸冷卻最后達(dá)到結(jié)晶狀態(tài)的物理過(guò)程，通過(guò)生成一系列參數(shù)向量模擬粒子的熱運(yùn)動(dòng)，并緩慢地減小模擬溫度的控制參數(shù)，最終達(dá)到系統(tǒng)能量最小值.該算法是局部搜索算法的擴(kuò)展，算法以一定的概率選擇鄰域中能量值比較大的狀態(tài)，理論上是一種全局最優(yōu)算法.Metropolis等人［2］最早于1953年提出模擬退火算法，1983年 Kirkpat rick等人［3］成功把它應(yīng)用于組合優(yōu)化問(wèn)題，算法模仿退火的物理過(guò)程，不依賴初始條件的選擇，可尋找全局最小點(diǎn)而不陷入局部極小.

基本的模擬退火算法是:設(shè)當(dāng)前溫度為t，當(dāng)前狀態(tài)為P，其目標(biāo)函數(shù)值為h(P)，在P的鄰域N(P)內(nèi)產(chǎn)生一個(gè)新狀態(tài)P'，若h(P')≥h(P)，則P=P';否則在［0，1)上產(chǎn)生隨機(jī)數(shù)rand，計(jì)算，以概率 prob接受新狀態(tài)P=P'，否則舍去.重復(fù)以上過(guò)程，直到目標(biāo)值在當(dāng)前溫度下趨于一個(gè)穩(wěn)定值.

1.4 基于聚類分析的社團(tuán)探測(cè)算法(C－based SA)

對(duì)于1.1給出的G(V，E，W)，給定社團(tuán)數(shù)目的最大值kmax和最小值kmin，進(jìn)行以下步驟:

(1)記連接權(quán)矩陣W為D=(dij)n×n，其中D為對(duì)角矩陣，dii為第i個(gè)節(jié)點(diǎn)的度，n為節(jié)點(diǎn)數(shù).

(2)對(duì)滿足kmin≤k≤kmax的k，用Capocci方法［14］將尋找k社團(tuán)問(wèn)題轉(zhuǎn)化為數(shù)據(jù)的k聚類問(wèn)題.實(shí)際上是計(jì)算N=D－1W的前k－1個(gè)非平凡特征向量 e1，e2，…，ek－1(ei∈ Rn，i=1，…，k－1)組成矩陣A.由A的行向量x1，…xn，xi∈Rk)得到n個(gè)的數(shù)據(jù)向量形式的待聚類樣本.

(3)用模擬退火算法對(duì)上面得到的數(shù)據(jù)進(jìn)行k聚類:

這里對(duì)n個(gè)個(gè)體進(jìn)行二進(jìn)制編碼，根據(jù)n的大小確定個(gè)體的編碼長(zhǎng)度len，len=min{i|2i≥n}，定義鄰域結(jié)構(gòu):

這里的目標(biāo)函數(shù)選定為模塊度函數(shù)y=M(Pk)(Pk是對(duì)n個(gè)個(gè)體一個(gè)k劃分)，對(duì)相應(yīng)的模塊度函數(shù)進(jìn)行優(yōu)化迭代，每迭代一次時(shí)都需要首先將每個(gè)解解碼為聚類中心，然后將根據(jù)距離聚類中心最近的法則對(duì)每個(gè)個(gè)體進(jìn)行分類，得出的聚類結(jié)果還原為相應(yīng)的社團(tuán)結(jié)構(gòu).

設(shè)控制溫度參數(shù)的衰減系數(shù)λ;每一溫度下馬氏鏈的長(zhǎng)度都取為鄰域結(jié)構(gòu)的大小k len.

算法1:(1)隨機(jī)給定一個(gè)初始解x∈S，這里S為可行解集，y=M(Pk);

(2)while(t0＜tf)

(2.1)for(i=0;i＜;i++)

(2.1.1)t = floor(unifrnd(1，klen －0.0001))，令 x'=x ⊕ It，y'=M(Pk')

(2.1.2)delta(f)=y－y';

(2.1.3)若 delta(f)＞ =0，則x=x'，y=y';

否則，若exp(delta(f)/t0)＞ random(0，1)，則 x=x'，y=y';

(2.2)t0=λ·t0;.

(3)輸出:SA算法最優(yōu)解x.

(4)對(duì)滿足kmin≤ k≤kmax的 k重復(fù)(2)、(3)，最后比較得到使目標(biāo)函數(shù)最大的k聚類，并根據(jù)聚類結(jié)果還原為對(duì)應(yīng)的社團(tuán)結(jié)構(gòu).

2 試驗(yàn)結(jié)果

該文用海峽四川釣友聯(lián)誼會(huì)(http://bbs.chinafishing.com/forum－113－1.html)的實(shí)際數(shù)據(jù)驗(yàn)證1.1和1.4中的算法.海峽四川釣友聯(lián)誼會(huì)是海峽釣魚網(wǎng)的一個(gè)子板塊，其中參與者大部分為四川本地釣魚愛好者，論壇成員具有共同的興趣愛好.該板塊為四川釣魚愛好者的學(xué)習(xí)與交流提供了一條新途徑.針對(duì)相關(guān)主題，論壇成員可以提出問(wèn)題、發(fā)表各自的觀點(diǎn)和看法，相互交流，相互幫助.

實(shí)際數(shù)據(jù)處理時(shí)，根據(jù)對(duì)已掌握的id對(duì)應(yīng)關(guān)系，對(duì)部分id進(jìn)行了特別處理，例如將“清涼油”和“151”這2個(gè)id合并處理，將“被草壓死的駱駝”與“駱駝”，“黑武器”與“黑版”視為同一個(gè)id.

2.1 連接權(quán)矩陣的生成

按照1.1的算法，該文從6000余名在該論壇中發(fā)言的成員中篩選出滿足各種閾值條件的成員1436人，并生成對(duì)應(yīng)的連接權(quán)矩陣.

2.2 對(duì)比試驗(yàn)

為驗(yàn)證算法的有效性，該文將該論壇數(shù)據(jù)分別運(yùn)用 K － Means算法［14］、CNN 算法［15］以及該文的基于模擬退火的社團(tuán)探測(cè)算法.其中，KMeans算法是常見的聚類算法，是基于距離聚類中心最近法則為標(biāo)準(zhǔn)對(duì)個(gè)體進(jìn)行分類的;而CNN算法則采用競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)模型，進(jìn)行無(wú)監(jiān)督學(xué)習(xí)的分類.這里要注意的是，所有數(shù)據(jù)都經(jīng)過(guò)1.4中第一步和第二步處理后，分別運(yùn)行相應(yīng)的算法，這里所有的算法程序都用matlab編寫.

表1給出了各算法的試驗(yàn)對(duì)比結(jié)果.

表1 試驗(yàn)對(duì)比結(jié)果

這里運(yùn)行次數(shù)為得到最優(yōu)解的平均運(yùn)行次數(shù)，時(shí)間為平均運(yùn)行時(shí)間.

表2給出了應(yīng)用C－based SA算法模塊度在0.36以上的聚類結(jié)果，k=3、4、5時(shí)模塊度較高.

表2 試驗(yàn)結(jié)果

圖1給出了k=5、λ=0.997時(shí)的探測(cè)算法的迭代過(guò)程，迭代到2300次左右就已經(jīng)求出了最優(yōu)解.

圖1 模擬退火社團(tuán)探測(cè)算法迭代過(guò)程(k=5，λ =0.997)

2.3 結(jié)果分析

通過(guò)對(duì)實(shí)際數(shù)據(jù)運(yùn)行3種不同的社團(tuán)探測(cè)算法，結(jié)果表明:K－Means算法速度較快，但受初始化條件影響較大，可靠性也比其他兩種算法差，網(wǎng)絡(luò)規(guī)模擴(kuò)大對(duì)算法性能影響較大;CNN算法對(duì)初始化條件依賴程度較K－Means算法較低，但運(yùn)算速度較慢，并且對(duì)數(shù)據(jù)預(yù)處理需要花較長(zhǎng)的時(shí)間;三種算法中，C－based SA算法不依賴初始化條件的選取，直接使用模塊度函數(shù)作為目標(biāo)函數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)探測(cè)，能保證達(dá)到全局最優(yōu)解，可靠性較其他兩種算法要高，該算法的復(fù)雜度依賴于系統(tǒng)降溫速率的設(shè)置，其缺點(diǎn)是運(yùn)行時(shí)間較長(zhǎng).

3 結(jié)束語(yǔ)

提出了針對(duì)網(wǎng)絡(luò)論壇的社交網(wǎng)絡(luò)的構(gòu)建方法，將組合優(yōu)化的方法與聚類分析的思想相互結(jié)合并應(yīng)用到網(wǎng)絡(luò)論壇社團(tuán)結(jié)構(gòu)的求取上，并提出了用模擬退火算法來(lái)求解，解決了實(shí)際工作實(shí)踐中遇到的問(wèn)題.試驗(yàn)結(jié)果驗(yàn)證了算法的準(zhǔn)確性，模擬退火算法與聚類分析的思想能有效的結(jié)合起來(lái)，對(duì)論壇社團(tuán)結(jié)構(gòu)進(jìn)行分析有較大的實(shí)用價(jià)值.

試驗(yàn)結(jié)果同時(shí)說(shuō)明，基于興趣的網(wǎng)絡(luò)論壇中的社交網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)不太明顯，值得注意的是，該文使用的是非重疊性的社團(tuán)探測(cè)算法，考慮到實(shí)際網(wǎng)絡(luò)中，個(gè)體往往具有多群體特性，因此，改進(jìn)社團(tuán)結(jié)構(gòu)的定義以及在此基礎(chǔ)上探索新的社團(tuán)劃分方法是一個(gè)值得研究的方向.

［1］ Xie Zhou，Wang Xiaofan.An Overview of Algorithms for Ana lyz ing Community Structure in Complex Networks.Complex Systems and Complexity Science，2005(8):46－50.

［2］ Metropolis N，Rosenbluth A W.Rosenbluth M N，et al.E－quations of state calculations by fast computing machines.J Chemical Physics，1953(21):1087－1091.

［3］ Kirkpatrick S，Gelatt C D，Jr M P.Vecchi Optimization by Simulated Annealing［J］.SCIENCE，1983，220(5):4598 －4602.

［4］ 邢文訓(xùn) 謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.北京:清華大學(xué)出版社，2003.

［5］ 趙天玉.模擬退火算法及其在組合優(yōu)化中的應(yīng)用［J］.計(jì)算機(jī)與現(xiàn)代化，1999，61(3).

［6］ CapocciA，Servedio V D P，Caldarelli G，et al.Detecting communities in large networks［J］.Physica A，2005，352(2－4):669－676.

［7］ Clauset A，NewmanM E J，Moore C.Finding community structure in very large networks［J］.Phys Rev E，2004，7(6):066111.

［8］ Bezdek J C，Boggavarapu S，Hall L O，et al.Genetic algorithm guided clustering［J］.FUZZ2IEEE＇94，1994(2):34－39.

［9］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Phys Rev E，2004，69(2):026113.

［10］ White S，Smyth P.A spectral clustering app roach to finding communities in graphs［C］.Newport Beach，USA:SIAM International Conference on DataMining，2005.

［11］王陸，馬如霞.意見領(lǐng)袖在虛擬學(xué)習(xí)社區(qū)社會(huì)網(wǎng)絡(luò)中的作用［J］.電化教育研究，2009，(1):54－58.

［12］葉新東，邱峰，沈敏勇.教育技術(shù)博客的社會(huì)網(wǎng)絡(luò)分析［J］.現(xiàn)代教育技術(shù)，2008(5):36 －41.

［13］胡勇，張翀斌，等.網(wǎng)絡(luò)輿論形成過(guò)程意見領(lǐng)袖形成模型研究.四川大學(xué)學(xué)報(bào):自然科學(xué)版，2008，45(2):347－351.

［14］ Capocci A，Munoz M A.Detecting network communities:a new systematic and efficient algotithm ［J］.Physica A，2005，352(2－4):669－676.

［15］ 周開利，康耀紅.神經(jīng)網(wǎng)絡(luò)模型及其MATLAB仿真程序設(shè)計(jì)［M］.北京，清華大學(xué)出版社，2005.111－128.