可變聚類無標度網絡上的謠言免疫策略

何郁郁， 鄒艷麗， 許旋風， 鄭 京

（廣西師范大學電子工程學院，廣西桂林 541004）

可變聚類無標度網絡上的謠言免疫策略

何郁郁， 鄒艷麗*， 許旋風， 鄭 京

（廣西師范大學電子工程學院，廣西桂林 541004）

提出一種聚類免疫策略，使用改進的經典謠言傳播模型，在可變聚類無標度網絡上研究其免疫效果.研究發現，聚類免疫的效果隨著網絡聚類系數的增加而變好.在不同聚類系數下，比較目標免疫、介數免疫、緊密度免疫和聚類免疫的免疫效果發現，無論網絡的聚類特性如何，介數免疫始終是幾種免疫策略中效果最好的，當網絡聚類系數較大時，聚類免疫的效果超過緊密度免疫接近目標免疫，進一步增大網絡的聚類系數，聚類免疫的效果超過目標免疫而接近介數免疫.

聚類系數；免疫；謠言傳播模型；可變聚類無標度網絡

0 引言

謠言，指的是沒有相應事實基礎、卻被捏造出來并通過一定手段推動傳播的言論.當有害的謠言在社會網中傳播時，能引起人們的恐慌，給社會帶來經濟損失.因特網的普及和發展，在給人們帶來便利的同時，也加速了謠言的傳播.最近網絡謠言的傳播已給社會秩序帶來了嚴重的影響.因此尋找一種能抑制謠言在社會網中傳播的機制，變得越來越重要.

Daley和Kendall［1］于1964年首先提出謠言傳播的數學模型（DK模型），而后Maki和Thomson［2］在此基礎上提出MT模型.但DK模型和MT模型的缺點是都沒有考慮網絡的拓撲結構.Zanette［3－4］最早在復雜網絡上建立謠言傳播模型，并在小世界網絡中得出了謠言傳播存在臨界值的結論.Moerno［5］等人發展了DK模型，同時把由計算機仿真與通過數學分析方法得出的結論進行比較［6］.Anurag Singh［7－8］對Moerno的模型進行修改，將免疫人群進一步分為接受但不傳播謠言和拒絕且不傳播謠言兩類，并以此模型為基礎，對小世界網絡和無標度網上的隨機免疫和目標免疫進行研究.

前人對復雜建模進行了大量研究［9－13］，發現現實世界中許多網絡既具有冪律度分布，又具有高聚類性質.而WS小世界網絡雖具有高聚類、短平均路徑性質，但網絡度分布卻不服從冪律分布；BA網絡雖具有冪律分布，但其網絡聚類系數卻很低.因此Holme［14］等人提出了一種聚類系數可變的無標度網絡模型，該模型可生成同時具有冪律度分布和較高聚類系數的網絡.

免疫是控制謠言在網絡中傳播的有效方法.潘灶烽［15］等人研究了謠言在可變聚類系數無標度網絡上的傳播過程，發現通過增大網絡聚類系數可以有效地抑制謠言傳播.受此啟發，提出一種新的聚類免疫方法，然后使用改進的SIR模型，在可變聚類系數無標度網絡上研究抑制謠言傳播的效果.通過改變網絡的聚類系數，分析聚類免疫效果與網絡聚類特性的關系，并對聚類免疫和其他幾種免疫策略的免疫效果進行了比較.

1 網絡模型及謠言模型

1.1 可變聚類系數無標度網絡模型

研究謠言傳播和免疫采用的網絡模型是聚類系數可調的無標度網絡模型，該模型是Holme等人為了補充小世界網絡和無標度網絡的不足而提出的.該模型通過對BA網絡的生成規則進行修改，可以得到同時具有冪律度分布和較高聚類系數的網絡.

可變聚類系數無標度網絡的生成法則為：初始時，網絡有m0＝m＋1個全連接的節點，之后每個時步網絡新增一個與網絡有m條連邊的新節點i．節點i先采用與BA網絡模型相同的優先連接法則，和網絡中已存在的節點j做一次優先連接．為了增加網絡的聚類，接下來節點i將以概率pt隨機地與節點j的鄰居做三角連接，如果節點j的所有鄰居都已經和節點i相連，那么節點i將會以1－pt的概率做優先連接，直到m條連邊都添加完，網絡再添加下一個新節點.

通過分析可以發現，可變聚類系數無標度網絡的聚類系數主要與三角連接概率pt有關．當概率pt增加時，網絡新增節點做三角連接的概率增加，節點鄰居互為鄰居的概率增大，從而網絡整體聚類系數增加.而當pt為0時，可變聚類網絡則退化為BA網絡.

1.2 謠言傳播模型

經典的SIR謠言傳播模型是將所有的人群分為三類：無知個體（Ignorants）、傳播者（Spreaders）和免疫者（Stiflers）.其中，無知人群是指容易受信息影響的人群，傳播者是指散播謠言的人群，而免疫者是指聽過謠言但對謠言傳播失去興趣的人群.Anurag Singh等［7］對經典模型進行修改，將免疫者又進一步分為兩類：一類是接受謠言但沒興趣傳播的人群；另一類是拒絕謠言人群（對謠言不感興趣不接受，此類可視為傳播模型中的免疫人群）.假設網絡中共有N個節點，每個節點都可能具有：無知、傳播、接收但不傳播和拒絕且不傳播，這四種狀態中的其中一種.謠言傳播過程為：當一個傳播者與一個處于無知狀態的節點相連時，此無知節點可能會以λ的概率變成一個傳播者，也可能以α的概率變為一個接受但不傳播謠言的免疫者，還可能以δ的概率變為一個拒絕且不傳播謠言的免疫者；但一個傳播者與一個處于傳播狀態或免疫狀態的節點相連時，那個主動發起謠言傳播的節點會以γ的概率變成一個接受但不傳播謠言的免疫者．在此，1－δ可以認為是謠言的可信度，δ越大，1－δ越小，表示謠言聽起來越不可信，因此無知者拒絕謠言的可能性越大．參數λ、α和δ滿足λ＋α＋δ≤1．

定義I（t）、S（t）、Racc（t）和Rrej（t）分別代表在t時刻，無知節點、傳播節點、接受但不傳播的免疫節點和拒絕且不傳播的免疫節點的數量占總人口的比例.顯然有I（t）＋S（t）＋Racc（t）＋Rrej（t）＝1．〈k〉表示網絡的平均度，此模型的平均場方程為［7］

2 免疫策略

免疫是控制謠言在網絡中散布的有效方法，而根據網絡的特性選擇有效免疫策略對于控制謠言的散布可以起到事半功倍的效果.在這里，假設網絡規模為N，免疫人口比例為g，則在初始時，網絡中有g×N個節點處于免疫狀態.

2.1 已有的免疫策略

常用的免疫策略有隨機免疫、目標免疫、鄰居免疫［16］、節點介數免疫、緊密度免疫等［20］.最近還有學者研究了通過K核分解的方法去尋找網絡中最具影響力的節點［17－20］.我們計算發現，研究的可變聚類網絡中，應用K核分解方法得到網絡中節點的核數值均為m，因此該方法不能區分這類網絡中節點的重要性，所以暫不考慮K核免疫.下面介紹本文研究的幾種免疫策略.

1）目標免疫 由于在無標度網絡中，目標免疫優于鄰居免疫、鄰居免疫優于隨機免疫［8］，所以只研究目標免疫.目標免疫是指對網絡中大度節點進行免疫，使用此免疫方法時，需要對網絡節點按照度的大小進行降序排列，然后選取排在前面的g×N個節點進行免疫.

2）節點介數免疫 節點介數是指網絡中通過該節點的最短路徑條數［21］.介數主要用于衡量節點在信息傳播中的重要性.節點介數免疫法是先求出網絡中每個節點的介數，然后對網絡中的節點按照介數的大小進行降序排列，選取排在前面的g×N個節點進行免疫.

3）緊密度免疫 節點i的緊密度定義為該節點到網絡中其余N－1個節點的最短路徑和的倒數.節點緊密度主要用于刻畫節點到其它節點的難易程度［20］.緊密度免疫是指對網絡中的節點按照其緊密度大小進行降序排列，選取排在前面的g×N個節點進行免疫.

2.2 聚類免疫

本文主要在可變聚類系數無標度網絡上研究謠言的免疫策略.文獻［15］的研究表明，增大聚類系數可以有效地抑制謠言傳播，由此可見，網絡的聚類系數可能和免疫效果之間存在一定的關系，因此，提出一種聚類免疫法.

網絡上一個節點的聚類系數是指該節點的鄰居間互為鄰居的概率.假設網絡中的一個節點i有ki個鄰居，那么這些鄰居間最多可能有ki（ki－1）／2條邊，而這ki個節點間實際存在的邊數為Ei，那么節點i的聚類系數定義為［21］

聚類免疫策略為：將網絡中節點按照聚類系數大小進行降序排列，選取排在前面的g×N個節點進行免疫.

3 仿真實驗結果

按照1.1的生成規則生成一個節點個數N＝2 000的可變聚類網絡.令網絡中的每個節點都處于無知、傳播、接受但不傳播和拒絕且不傳播四種狀態中的一種狀態，采用1.2節描述的Anurag Singh等提出的謠言傳播模型，在t＝0時刻，在網絡中隨機選擇一個節點作為傳播者，然后根據不同免疫策略，選擇g×N個節點作為免疫節點（狀態為拒絕且不傳播謠言），剩下的全為無知節點．t＝1時，謠言開始傳播，令I（t）、S（t）、Racc（t）和Rrej（t）分別表示在t時刻，無知節點、傳播節點、接受但不傳播的免疫節點和拒絕且不傳播的免疫節點的數量占總人口的比例．謠言模型參數設置為λ＝0.25、α＝0、δ＝0、γ＝0.25．傳播結束后，網絡中接受但不傳播謠言的節點比例Racc（t）是網絡5次生成、每次生成100次實驗的平均值.

謠言模型中參數α和δ設置為零，是為了避免當傳播者與無知者接觸時，無知者變成Racc態和Rrej態的情況．當傳播過程結束后，網絡中Rrej態節點全為初始時的免疫節點；而Racc態節點，則全由傳播者與傳播者或免疫者接觸后變化而成，這時得到的Racc節點比例更能充分體現免疫對謠言傳播造成的影響.

3.1 聚類免疫效果和聚類系數的關系

三角連接概率pt取值的大小直接影響網絡的聚類系數．當網絡初始節點m0＝3，每新增一個節點增加連邊數m＝2時，網絡平均度〈k〉≈4；當網絡初始節點數m0＝7，每新增一個節點增加連邊數m＝6時，網絡平均度〈k〉≈12．圖1分別畫出了網絡平均度在〈k〉≈4和〈k〉≈12時，不同pt對應的網絡聚類系數．由圖1可見，在網絡連接較稀疏時，改變pt可以在較大范圍里調解網絡的聚類系數；當網絡連接較密時，改變pt，網絡的聚類系數變化范圍不大.

那么對聚類特性不同的網絡，提出的聚類免疫效果會有什么不同呢？圖2為網絡平均度分別為〈k〉≈4和〈k〉≈12時，采用聚類免疫策略，謠言傳播結束后，網絡中接受但不傳播謠言的節點比例Racc隨初始免疫節點比例g的變化.

圖1 不同三角連接概率下網絡聚類系數Fig.1 Network clustering coefficient with different triangle connection probability

圖2 不同網絡平均度下接受但不傳播謠言節點比例Racc隨聚類免疫比例g的變化Fig.2 Proportion of Racc Node that accept but do not spread rumors as functions of clustering immune proportion g in networks with different average degree

由圖2可知，當網絡平均度〈k〉≈4時，聚類免疫效果隨網絡聚類系數的增加而增強．當pt＝0時，網絡聚類系數為0.016 094，聚類免疫臨界gc≈0.55；而當pt增大到0.9時，網絡聚類系數為0.643 386，聚類免疫臨界gc≈0.05，可見在連接較稀疏的可變聚類無標度網絡上，聚類免疫臨界值隨網絡聚類系數的增加而減小．但當網絡平均度〈k〉≈12時，pt在取值范圍［0，0.7］內得到的免疫效果幾乎相同，免疫臨界值gc≈0.85；而當pt＝0.9時，免疫效果雖有所改善，但免疫臨界值也接近0.7.因此當可變聚類網絡平均度較小，網絡連接較稀疏時，聚類免疫效果隨聚類系數增加而增強，免疫有效；當平均度較大時，聚類免疫失效.

3.2 聚類免疫和其它免疫效果比較

由于聚類免疫在連接較稀疏的網絡上有效，我們在平均度約為4的可變聚類網絡上對聚類免疫、介數免疫、目標免疫和緊密度免疫等幾種免疫方法的效果進行比較.我們分別做出了pt取值為0、0.1、0.3、0.5、0.7和0.9時，幾種免疫策略的效果圖，如圖3所示.由圖3（a）可見，當pt＝0時，可變聚類網絡恢復為BA無標度網絡，其聚類系數較小約為0.016，此時聚類免疫效果比其他幾種免疫策略效果差；但隨著pt的增大，網絡聚類系數的增加，聚類免疫的效果變得越來越好，當pt≥0.3時，聚類免疫的效果已經超過緊密度免疫接近目標免疫；當pt≥0.5時，聚類免疫的效果已經超過目標免疫；當pt≥0.7時，聚類免疫的效果已經接近介數免疫；進一步增大聚類系數，我們發現當pt≥0.9時，網絡上聚類免疫、目標免疫和介數免疫的效果幾乎相同，緊密度免疫效果較差.因此通過在可變聚類系數網絡上對幾種免疫策略的對比，我們發現無論聚類系數如何，介數免疫始終是最好的，目標免疫次之，當網絡聚類特性較強時，可采用聚類免疫.

4 結論

提出一種聚類免疫策略，并使用改進的經典謠言傳播模型，在可變聚類系數無標度網絡上研究該免疫策略的有效性.研究發現，當網絡連接較稀疏、網絡平均度較小時，聚類免疫的效果隨著網絡聚類系數的增加而增強；當網絡連接較緊密，網絡平均度較大時，聚類免疫失效.接著我們對網絡連接較稀疏時，不同聚類系數下，聚類免疫、介數免疫、目標免疫和緊密度免疫這幾種免疫策略的效果進行了比較.比較研究發現，無論網絡聚類特性如何，介數免疫始終是四種免疫方法中最好的，當聚類系數較大時，聚類免疫的效果超過緊密度免疫和目標免疫而接近介數免疫.因此聚類免疫適用于連接較稀疏，聚類系數較大的無標度網絡.本文的研究對于如何在高聚類網絡中選擇免疫策略，避免謠言大規模傳播具有一定的指導意義.

圖3 不同網絡聚類系數下，幾種免疫策略的效果Fig.3 Effects of immunization strategies in networks with different clustering coefficient

［1］ Daley D J，Gani J.Epidemic modelling：An introduction［M］.Cambridge，UK：Cambridge University Press，2001：9－30.

［2］ Maki D P，Thomson M.Mathematical models and applications：With emphasis on the social，life，and management sciences［M］.New Jersey：Prentice—Hall（Englewood Cliffs，N J），1973：23－100.

［3］ Zanette D H.Critical behavior of propagation on small-world networks［J］.Physical Review E，2001，64（5）：1－4.

［4］ Zanette D H.Dynamics of rumor propagation on small-world networks［J］.Physical Review E，2002，65（4）：1－9.

［5］ Moreno Y，Nekovee M，Pacheco A F.Dynamics of rumor spreading in complex networks［J］.Physical Review E，2004，69（6）：1－7.

［6］ 張芳，司廣亞，羅批.謠言傳播模型研究綜述［J］.復雜系統與復雜性科學，2009，6（4）：1－11.

［7］ Singh A，Singh Y N.Rumor spreading and inoculation of nodes in complex networks［C］∥Proceedings of the 21st International Conference Companion on World Wide Web，New York，USA，ACM，2012：675－678.

［8］ Singh A，Kumar R，Singh Y N.Rumor dynamics with acceptability factor and inoculation of nodes in scale free networks［C］∥Eighth International Conference on Signal Image Technology and Internet Based Systems，IEEE，2012：798－804.

［9］ Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45（2）：167－256.

［10］ 周濤，柏文潔，汪秉宏，劉之景，嚴鋼.復雜網絡研究概述［J］.物理，2005，34（1）：31－36.

［11］ Boccaletti S，Latora V，Moreno Y，Chavez M，Hwang D U.Complex networks：Structure and dynamics［J］.Physics Reports，2006，424（4－5）：175－308.

［12］ Tang Shengxue，Chen Li，Huang Jiaoying.Modeling and identification of associated complex networks［J］.Chinese J Comput Phys，2012，29（2）：308－316.

［13］ Qiao Jian，Fan Ying，Li Guoying.Cause analysis of growing and non-growing scale-free networks［J］.Chinese J Comput Phys，2013，30（2）：309－316.

［14］ Holme P，Kim B J.Growing scale-free networks with tunable clustering［J］.Physical Review E，2002，65（2）：1－4.

［15］ 潘灶烽，汪小帆，李翔.可變聚類系數無標度網絡上的謠言傳播仿真研究［J］.系統仿真學報，2006，18（8）：2346－2348.

［16］ Cohen R，Havlin S，Avraham D B.Efficient immunization strategies for computer networks and populations［J］.Physical Review Letters，2003，91（24）：1－4.

［17］ Kitsak M，Gallos L K，Havlin S，Liljeros F，Muchnik L，Stanley H E，Makes H A.Identification of influential spreaders in complex networks［J］.Nature Physics，2010，6：888－893.

［18］ Liu J G，Ren Z M，Guo Q.Ranking the spreading influence in complex nerwork［J］.Physica A，2013，392（18）：4154－4159.

［19］ 任卓明，劉建國，邵鳳，胡兆龍，郭強.復雜網絡中最小K－核節點的傳播能力分析［J］.物理學報，2013，62（10）：1－6.

［20］ 胡慶成，尹龑燊，馬鵬斐，高旸，張勇，邢春曉.一種新的網絡傳播中最有影響力的節點發現方法［J］.物理學報，2013，62（14）：1－11.

［21］ 汪小帆，李翔，陳關榮.復雜網絡理論及其應用［M］.第一版.北京：清華大學出版社，2006：72－97.

Immunity of Rumor on Scale-free Network with Tunable Clustering

HE Yuyu， ZOU Yanli， XU Xuanfeng， ZHENG Jing
（College of Electronic Engineering，Guangxi Normal University，Guilin 541004，China）

We present a cluster immunization strategy and study its immune effect on scale-free network with tunable clustering in a modified classic rumor propagation model.Study shows that effect of cluster immunization becomes better with increasing of network clustering coefficient.Severalimmunizationstrategiesincludingtargetimmunization，betweennessimmunization，closeness immunization and cluster immunization are compared.It shows that betweenness immunization is always the best regardless of network clustering.As a network clustering coefficient is relatively great，effect of cluster immunization is better than that of closeness immunization and close to target immunization.With further increasing network clustering coefficient，cluster immunization exceeds target immunization and approaches to betweenness immunization.

cluster coefficient；immunity；rumor spreading model；scale-free network with tunable clustering

date： 2013－11－15；Revised date： 2014－01－28

TP391

A

2013－11－15；

2014－01－28基金項目：國家自然科學基金（11062001，11165003）資助項目作者簡介：何郁郁（1988－），女，碩士生，主要從事復雜網絡上的信息傳播及免疫策略研究

*通訊作者：鄒艷麗（1972－），女，教授，博士，從事復雜網絡理論及其應用研究，E-mail：zouyanli72＠163.com

1001-246X（2014）06-0751-06