一類具有社團性質的二分網絡

王劍凌 ，陳慶華

（1.福建江夏學院數理教研部，福建福州，350108；2.福建師范大學數學與計算機科學學院，福建福州， 350117）

復雜網絡由節點和邊組成，節點代表元素，邊代表元素間的相互作用。復雜網絡廣泛應用于經濟、工程、生物等社會的各個領域，比如，國與國之間的經濟合作關系可以描述為世界貿易網，新陳代謝網能量化蛋白質之間的相互作用，人與人之間的相互關系構成人際關系網等。復雜網絡在現實生活中發揮著舉足輕重的作用，成為近年來學者研究的熱點。

實證表明大多數實際網絡具有一些共同的特征：網絡規模龐大且結構復雜，演化過程具有隨機性；網絡是開放的，不斷增加節點和邊，實現網絡增長；任意兩個節點之間存在短路徑，平均路徑長度呈對數增長，且有明顯的群聚趨勢；網絡具有冪律尾部，節點間度相關，存在極少數中樞點；隨機去除有少數連邊的節點，不會改變網絡的拓撲結構。

在此基礎上，不少學者對模型進一步改進，更接近實際網絡，如局部世界網絡[3]、加權網絡[4,5]等模型。Chen等考慮到節點的初始吸引力、重新布線等因素，對模型進行擴展，來研究無標度網絡的生成機制[6]。Guillaume等提出很多實際網絡都可視為二分網絡，尤其是演員——電影、學生——課程、科研人員——文章等具有二分圖結構的網絡[7]。Xu等提出的社團網絡，考慮到科學家合作關系不僅局限在同一領域，還有不同領域間的合作[8]。Furuya等根據醫學院提供的處方記錄，提出了DPN網絡來描述藥物之間的關系[9]。此外，對度分布的計算也有四種常見的方法：平均場方法[10]、率方程方法[11]、主方程方法[12]、馬氏鏈方法[13,14]。本文基于Xu等的社團網絡和Furuya等的DPN網絡，提出一類具有社團性質的二分網絡，來描述醫生與藥物之間的關系。

一、演化模型

初始時刻，⊥中有M個孤立的社團，每個社團有n1個孤立的點， 中有n2個孤立的點，在⊥與之間有m條邊。

1.以概率p在⊥中隨機選擇一個區域加入新點，新點與 中n0個點連接的概率為

3.以概率r（=1-p-q）在⊥中隨機選擇一個區域中的一點，此點與中n0個點連接的概率同（※）

二、主要結論

定理2.1⊥的外部度分布具有冪律尾部，即

證明：在t時刻，的點數為，總點數為

根據平均場方法的假設，點i進入系統的時間ti服從[0,t]上的均勻分布，則有

證明：在t時刻，的點數為，總點數為

根據平均場方法的假設，點i進入系統的時間服從[0,t]上的均勻分布，則有

本文提出一類具有社團性質的二分網絡，含有可調節的參數p,q,r，解析結果表明⊥和的外部度分布都具有冪律尾部。

[1]Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393:440.

[2]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286:509-512.

[3]Li X,Chen G R.A local-world evolving network model[J].Physica A,2003,328:274-286.

[4]Yook S H,Jeong H,Barabási A L,Tu Y.Weighted evolving networks[J].Phys.Rev.Lett.,2001,86:5835-5838.

[5]Barrat A,Barthélemy M,Vespignani A.Modeling the evolution of weighted networks[J].Phys.Rev.E,2004,70:066149.

[6]Chen Q H,Shi D H.The modeling of scale free networks[J].Physica A,2004,335:240-248.

[7]Guillaume J L,Latapy M.Bipartite structure of all complex networks[J].Information Processing Letters,2004,90:215-221.

[8]Xu X J,Zhang X,Mendes J F F.Growing community networks with local events[J].Physica A,2009,388:1273-1278.

[9]Furuya S,Yakubo K.Scale-free property of local-world networks and their community structure[J].Physica A,2010,389:5878-5886.

[10]Barabási A L,Albert R,Jeong H.Mean-field theory for scale-free random networks[J].Physica A,1999,272:173-187.

[11]Krapivsky P L,Redner S,Leyvraz F.Connectivity of growing Random networks[J].Phys.Rev.Lett.,2000,85:4629-4632.

[12]Dorogovtsev S N,Mendes J F F,Samukhin A N.Structure of growing networks with preferential linking[J].Phys.Rev.Lett.,2000,85:4633-4636.

[13]Shi D H,Chen Q H.Markov chain-based numerical method for degree distributions of growing networks[J].Physical Review E,2005,71:036140.

[14]Chen Q H,Shi D H,Markov chains theory for scale free networks[J].Physica A,2006,360:121-133.