摘  要： 以社交網(wǎng)絡(luò)中備受關(guān)注的通話社交網(wǎng)絡(luò)為研究對(duì)象，對(duì)其社團(tuán)結(jié)構(gòu)進(jìn)行分析。提出一種基于模糊綜合評(píng)判分析通話社交網(wǎng)絡(luò)權(quán)重的方法，并改進(jìn)CNM算法進(jìn)行社團(tuán)劃分。初步演示了通話社交網(wǎng)絡(luò)的演化規(guī)律，為深入研究通話社交網(wǎng)絡(luò)打下了堅(jiān)實(shí)基礎(chǔ)。
關(guān)鍵詞： 通話社交網(wǎng)絡(luò)；加權(quán)網(wǎng)絡(luò)；模糊綜合評(píng)判方法；社團(tuán)結(jié)構(gòu)；改進(jìn)的CNM算法

    雖然現(xiàn)實(shí)世界的復(fù)雜系統(tǒng)形式、功能各不相同，但其對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)卻有很大的相似性。從個(gè)體層面的度、聚集系數(shù)，到整體層面的度分布、整體聚集系數(shù)等，處于中間的描述就是社團(tuán)結(jié)構(gòu)描述。借助復(fù)雜網(wǎng)絡(luò)理論分析方法，科學(xué)家們成功地研究了社交網(wǎng)絡(luò)。Onnela[1-2]從工作、家庭、休閑等方面分析了社交網(wǎng)絡(luò)的結(jié)構(gòu)，由此發(fā)現(xiàn)相互連接的強(qiáng)度和網(wǎng)絡(luò)局域結(jié)構(gòu)的關(guān)系。Szabo和Barabasi[2]研究表明由不同的通話網(wǎng)絡(luò)發(fā)現(xiàn)兩個(gè)不同地區(qū)的同一社交網(wǎng)絡(luò)具有或強(qiáng)或弱的社團(tuán)隔離效應(yīng)的共性。Palla、Barasi和Vicsek[3-4]通過(guò)通話數(shù)據(jù)研究社會(huì)群體的演變發(fā)現(xiàn)。利用復(fù)雜網(wǎng)絡(luò)理論分析社交網(wǎng)絡(luò)拓?fù)湫再|(zhì)并進(jìn)行社團(tuán)分解為進(jìn)一步揭示通話社交網(wǎng)絡(luò)的演化規(guī)律打下了基礎(chǔ)。
    社團(tuán)結(jié)構(gòu)劃分算法的研究發(fā)展至今取得了很大的進(jìn)展。早期的研究包括Kernighan-Lin算法、譜平分法和分級(jí)聚類方法等[5]。但在大規(guī)模及超大規(guī)模的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分析中，算法時(shí)間復(fù)雜度和精確度的矛盾一直未能解決。目前，事先在不知道社團(tuán)數(shù)目的情況下，最快算法的時(shí)間復(fù)雜度為O(nlog2n)[6]。通話社交網(wǎng)絡(luò)屬于大規(guī)模加權(quán)網(wǎng)絡(luò)，其中權(quán)重的分布是研究該網(wǎng)絡(luò)的重要因素之一。本文提出一種基于模糊綜合評(píng)判的方法來(lái)評(píng)價(jià)通話網(wǎng)絡(luò)的權(quán)重，同時(shí)改進(jìn)CNM算法使其適用于加權(quán)網(wǎng)絡(luò)，并對(duì)現(xiàn)實(shí)加權(quán)通話社交網(wǎng)絡(luò)進(jìn)行實(shí)證研究。
1 通話社交網(wǎng)絡(luò)建模
    隨機(jī)抽取某月某地發(fā)生通話行為的號(hào)碼對(duì)。通話網(wǎng)絡(luò)本身是一個(gè)有向網(wǎng)絡(luò)，但若將此網(wǎng)絡(luò)視為信息網(wǎng)絡(luò)用作信息交流時(shí)，可把它當(dāng)作無(wú)向網(wǎng)絡(luò)。將通話加權(quán)網(wǎng)絡(luò)中的用戶抽象為圖的節(jié)點(diǎn)，只要兩個(gè)節(jié)點(diǎn)間有一次通話，就用一條邊相連(即圖的邊)。考慮實(shí)驗(yàn)機(jī)器的運(yùn)行速度，抽取某運(yùn)營(yíng)商2011年1月某地通話數(shù)據(jù)，其中包含的節(jié)點(diǎn)數(shù)為344 522，邊數(shù)為697 489。通過(guò)計(jì)算通話數(shù)據(jù)中的通話時(shí)長(zhǎng)、次數(shù)、頻度等特性以建立加權(quán)通話網(wǎng)絡(luò)模型。該加權(quán)通話網(wǎng)絡(luò)反應(yīng)某地區(qū)特定時(shí)間內(nèi)基于各種社會(huì)關(guān)系進(jìn)行過(guò)信息交流的狀態(tài)。
    構(gòu)建的通話社交網(wǎng)絡(luò)抽象為由點(diǎn)集N和邊集M組成的圖G=(V，E)，其中節(jié)點(diǎn)數(shù)N=|V|=344 522，邊數(shù)M=|E|=697 489。由于網(wǎng)絡(luò)規(guī)模較大，考慮到相關(guān)工具的局限性，取部分節(jié)點(diǎn)與邊建立模型，如圖1所示。

    由于從某運(yùn)營(yíng)商所獲得的大量實(shí)驗(yàn)數(shù)據(jù)中包含外網(wǎng)的用戶，故在建立移動(dòng)通信關(guān)系網(wǎng)時(shí)不能較好地描述用戶間通話關(guān)系。建立移動(dòng)通信關(guān)系網(wǎng)絡(luò)時(shí)，應(yīng)濾掉外網(wǎng)聯(lián)系記錄，只保留網(wǎng)內(nèi)通話聯(lián)系記錄，確保網(wǎng)絡(luò)社團(tuán)的正確性，避免其偶然性。為反映用戶真實(shí)的通話行為，排除電話銷售和錯(cuò)誤撥號(hào)的行為。同時(shí)去除每次通話時(shí)長(zhǎng)小于3 s的記錄和服務(wù)號(hào)碼。當(dāng)然這些做法會(huì)造成一些負(fù)面影響，但由于研究的時(shí)間跨度相對(duì)較長(zhǎng)，所以造成的影響是有限的。
2 基于模糊綜合評(píng)判的通話社交網(wǎng)絡(luò)權(quán)重計(jì)算
2.1 加權(quán)網(wǎng)絡(luò)權(quán)重定義
    加權(quán)網(wǎng)絡(luò)中每條邊都具有度量連接強(qiáng)弱度的數(shù)值，為復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的關(guān)系和互相作用提供精確的描述方式。
    目前加權(quán)網(wǎng)絡(luò)有兩種表示權(quán)重的方式：相似權(quán)和相異權(quán)[7]。相似權(quán)的權(quán)重表示權(quán)重越大，節(jié)點(diǎn)間的關(guān)系越緊密，兩節(jié)點(diǎn)之間的距離就越小。相異權(quán)則相反，權(quán)重越大，兩點(diǎn)間的關(guān)系越疏遠(yuǎn)；權(quán)重越小則關(guān)系越緊密。通常權(quán)重定義方式有以下3種[8-9]。
    （1）常數(shù)權(quán)重
    若加權(quán)采用常數(shù)權(quán)重分布，即網(wǎng)絡(luò)中的每條邊權(quán)重均相等且為常數(shù)。由此可知，二元網(wǎng)絡(luò)是一種特殊的加權(quán)網(wǎng)絡(luò)。
    （2）服從指數(shù)分布的邊權(quán)重
    假設(shè)邊的權(quán)重服從指數(shù)分布，即φ(θ)=θe-θx，其中θ>0。服從指數(shù)分布的樣本值均大于零，它與實(shí)際網(wǎng)絡(luò)中邊權(quán)重均大于零的情形一致。
    （3）節(jié)點(diǎn)度乘積函數(shù)的邊權(quán)重
    設(shè)節(jié)點(diǎn)i與節(jié)點(diǎn)j的度分別為ki和kj，則連接這兩個(gè)節(jié)點(diǎn)的邊權(quán)重定義為：wij=(ki kj)α，其中α可有效地調(diào)節(jié)節(jié)點(diǎn)的強(qiáng)度大小。
2.2 通話社交網(wǎng)絡(luò)權(quán)重
    本文研究的通話社交網(wǎng)絡(luò)相似權(quán)wij范圍為[0，∞)，也可歸一化到[0，1]。由于該網(wǎng)絡(luò)的權(quán)值由通話頻度、通話時(shí)長(zhǎng)、通話次數(shù)等幾方面共同決定，以上方法難以準(zhǔn)確描述其權(quán)重，下面提出一種基于模糊綜合評(píng)判的方法[10]對(duì)其權(quán)重進(jìn)行定義。首先介紹模糊綜合評(píng)判方法的思想。
    模糊綜合評(píng)判是對(duì)多種因素影響的事物做出全面評(píng)價(jià)的一種有效的多因素決策方法。設(shè)U={u1，u2，…，un}為n種因素(或指標(biāo))，V={v1，v2，…，vm}為m種評(píng)判(或等級(jí))。

    圖3所示為3種算法在時(shí)間復(fù)雜度方面的對(duì)比。GN

    本文基于某地的通話數(shù)據(jù)記錄建立了一個(gè)大型的社交網(wǎng)絡(luò)，并將模糊綜合評(píng)判方法合理地應(yīng)用于所構(gòu)建的通話社交網(wǎng)絡(luò)邊權(quán)計(jì)算及評(píng)價(jià)中。為進(jìn)一步分析社會(huì)網(wǎng)絡(luò)的演化打下堅(jiān)實(shí)的基礎(chǔ)。
參考文獻(xiàn)
[1] ONNELA J P，SARAMAKI J，HYVONEN J，et al.Analysis of a large-scale weighted network of one-to-one human  communication[J].New Journal of Physics，2007，9(6)：179-184.
[2] ONNELA J P，SARAM KI J，HYVONEN J，et al.Structure  and tie strengths in mobile communication networks[J]. PNAS，2007，104(18)：7332-7336.
[3] SZABG，BARABSI A.Preprint physics[S].2006.
[4] PALLA G，BARABASI A L，VICSEK T.Quantifying social  groupe volution[J].Nature，2007(446)：664-667.
[5] 解，汪小帆.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)分解算法研究綜述[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005(3)：12.
[6] 駱志剛，丁凡，蔣小舟，等.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J].國(guó)防科技大學(xué)學(xué)報(bào)，2011，33(1)：47-52.
[7] 田柳，迪增加，姚虹.權(quán)重分布對(duì)加權(quán)網(wǎng)絡(luò)效率的影響[J]. 物理學(xué)報(bào)，2011，60(2)：1-5.
[8] 姚尊強(qiáng)，尚可可，許小可.加權(quán)網(wǎng)絡(luò)常用統(tǒng)計(jì)量[J].上海理工大學(xué)學(xué)報(bào)，2012，34(1)：18-26.
[9] 覃森，戴冠中，王林，等.不同權(quán)重定義下的靜態(tài)與動(dòng)態(tài)加權(quán)網(wǎng)絡(luò)的比較分析[J].西北工業(yè)大學(xué)學(xué)報(bào)，2007，25(5)：672-676.
[10] 楊永萍，李寶棟，常文春.基于模糊綜合評(píng)判方法的研究及應(yīng)用[J].蘭州工業(yè)高等專業(yè)學(xué)報(bào)，2006，13(3)：49-52.