摘  要： 以社交網絡中備受關注的通話社交網絡為研究對象，對其社團結構進行分析。提出一種基于模糊綜合評判分析通話社交網絡權重的方法，并改進CNM算法進行社團劃分。初步演示了通話社交網絡的演化規律，為深入研究通話社交網絡打下了堅實基礎。
關鍵詞： 通話社交網絡；加權網絡；模糊綜合評判方法；社團結構；改進的CNM算法

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

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

    圖3所示為3種算法在時間復雜度方面的對比。GN

    本文基于某地的通話數據記錄建立了一個大型的社交網絡，并將模糊綜合評判方法合理地應用于所構建的通話社交網絡邊權計算及評價中。為進一步分析社會網絡的演化打下堅實的基礎。
參考文獻
[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] 解，汪小帆.復雜網絡中的社團結構分解算法研究綜述[J].復雜系統與復雜性科學，2005(3)：12.
[6] 駱志剛，丁凡，蔣小舟，等.復雜網絡社團發現算法研究新進展[J].國防科技大學學報，2011，33(1)：47-52.
[7] 田柳，迪增加，姚虹.權重分布對加權網絡效率的影響[J]. 物理學報，2011，60(2)：1-5.
[8] 姚尊強，尚可可，許小可.加權網絡常用統計量[J].上海理工大學學報，2012，34(1)：18-26.
[9] 覃森，戴冠中，王林，等.不同權重定義下的靜態與動態加權網絡的比較分析[J].西北工業大學學報，2007，25(5)：672-676.
[10] 楊永萍，李寶棟，常文春.基于模糊綜合評判方法的研究及應用[J].蘭州工業高等專業學報，2006，13(3)：49-52.