林慧嫻，陸靜曄

基于代理的信息傳播網(wǎng)絡(luò)中的初始節(jié)點(diǎn)選擇

林慧嫻，陸靜曄

（南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京210003）

如何在各種網(wǎng)絡(luò)中選擇合適的節(jié)點(diǎn)作為初始節(jié)點(diǎn)從而達(dá)到傳播效果最大化已經(jīng)得到了廣泛的關(guān)注和研究，但是目前的研究大部分都局限于網(wǎng)絡(luò)結(jié)構(gòu)本身，忽略了節(jié)點(diǎn)的異構(gòu)性，從而缺乏實(shí)用價(jià)值?；贏BM實(shí)驗(yàn)?zāi)Ｐ停瑯?gòu)建了由具有異構(gòu)屬性和行為的節(jié)點(diǎn)構(gòu)成的信息傳播模型，在此基礎(chǔ)上，探討了各個(gè)因素對(duì)于節(jié)點(diǎn)重要性的影響。實(shí)驗(yàn)結(jié)果表明，綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)因素和節(jié)點(diǎn)異構(gòu)性因素能夠更有效地找到影響力大的節(jié)點(diǎn)。

社會(huì)網(wǎng)絡(luò)；信息傳播；代理；節(jié)點(diǎn)選擇

0　引言

社會(huì)多元化和網(wǎng)絡(luò)便捷化推動(dòng)了信息傳播的發(fā)展，如廣告信息的傳播，新政策法規(guī)的傳播，某個(gè)突發(fā)事件的傳播等。信息是在社會(huì)網(wǎng)絡(luò)中傳播的，之前的研究都是把社會(huì)網(wǎng)絡(luò)中的人抽象成同構(gòu)的節(jié)點(diǎn)進(jìn)行研究，如Fourt模型、Woodlock模型［1］、Mansfield模型［2］以及影響力很大的Bass模型［3］，而這些都是一種理想的假設(shè)，實(shí)際上社會(huì)個(gè)體是異構(gòu)的，他們具有不同的屬性，而且他們與社會(huì)網(wǎng)中其他個(gè)體的親密度也是不一樣的，而這些都會(huì)影響信息在由一個(gè)個(gè)異構(gòu)個(gè)體組成的社會(huì)網(wǎng)絡(luò)中的傳播。如何在各種網(wǎng)絡(luò)中選擇合適的節(jié)點(diǎn)作為初始節(jié)點(diǎn)從而達(dá)到傳播效果最大化已經(jīng)得到了廣泛的關(guān)注和研究。然而這些研究都是基于網(wǎng)絡(luò)中的節(jié)點(diǎn)是同構(gòu)的基礎(chǔ)上，沒(méi)有考慮現(xiàn)實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的異構(gòu)性。本文利用ABM［4］計(jì)算實(shí)驗(yàn)?zāi)Ｐ蛯⑿畔鞑ゾW(wǎng)絡(luò)的個(gè)體抽象成具有屬性和網(wǎng)絡(luò)連接的個(gè)體，研究了如何選擇合適的初始節(jié)點(diǎn)才能達(dá)到最佳傳播效果。

1　ABM計(jì)算實(shí)驗(yàn)?zāi)Ｐ图靶畔鞑?/h2>

1.1ABM計(jì)算實(shí)驗(yàn)?zāi)Ｐ?/p>

因微分方程的缺陷，人們提出利用ABM計(jì)算實(shí)驗(yàn)?zāi)Ｐ蛠?lái)研究網(wǎng)絡(luò)中不同的個(gè)體，并稱這些異構(gòu)的個(gè)體為代理。這些代理是社會(huì)網(wǎng)絡(luò)中最基本的單元，多個(gè)代理以及它們之間的連接就構(gòu)成了社會(huì)網(wǎng)絡(luò)。代理的定義如圖1所示。

圖1　代理的定義

1.2信息傳播

現(xiàn)實(shí)社會(huì)中無(wú)時(shí)無(wú)刻不進(jìn)行著信息的傳播，而現(xiàn)在學(xué)者主要是對(duì)信息傳播的一個(gè)分支——?jiǎng)?chuàng)新的傳播進(jìn)行研究。ROGERS E M給出了最具權(quán)威的定義：創(chuàng)新的傳播是指創(chuàng)新通過(guò)一段時(shí)間，經(jīng)由特定的渠道，在某一社會(huì)團(tuán)體的成員中傳播的過(guò)程［5］。ROGERS E M將創(chuàng)新傳播的過(guò)程劃分為認(rèn)知、說(shuō)服、決定、實(shí)施、確認(rèn)。不同社會(huì)個(gè)體對(duì)某個(gè)創(chuàng)新的態(tài)度及行為是不一定的，相對(duì)積極的個(gè)體更傾向于采納創(chuàng)新，并且采納時(shí)間較短。經(jīng)過(guò)研究，這些個(gè)體行為所形成的整體現(xiàn)象是創(chuàng)新的采納人數(shù)隨著時(shí)間呈現(xiàn)“S”形，即初期上升緩慢，隨著采納人數(shù)的增加，會(huì)有一個(gè)迅速上升的過(guò)程，而當(dāng)采納人數(shù)較多時(shí)，上升速度又會(huì)下降。

信息傳播與創(chuàng)新傳播有很多共同點(diǎn)，都是從一個(gè)或多個(gè)節(jié)點(diǎn)向其他節(jié)點(diǎn)傳播的過(guò)程，傳播效果受節(jié)點(diǎn)間的連接和屬性影響。傳播時(shí)采納人數(shù)隨著時(shí)間呈現(xiàn)“S”形。而信息傳播不考慮節(jié)點(diǎn)對(duì)信息的采納，即ROGERS E M對(duì)創(chuàng)新傳播劃分的五個(gè)部分不適用于信息傳播。信息傳播除了轉(zhuǎn)發(fā)外不需要個(gè)體采取現(xiàn)實(shí)性的行動(dòng)，所以信息傳播的過(guò)程相對(duì)要簡(jiǎn)單迅速。人們一般是接收到某個(gè)信息，然后對(duì)信息進(jìn)行判斷處理，最后決定是否轉(zhuǎn)發(fā)。所以可以把信息傳播的過(guò)程劃分為三個(gè)部分：接收、處理、決定。

2　基于ABM初始節(jié)點(diǎn)選擇

如何最大化傳播效果一直是人們關(guān)注的問(wèn)題。社會(huì)網(wǎng)絡(luò)中影響最大化問(wèn)題（即如何選擇k個(gè)種子節(jié)點(diǎn)，使其在傳播過(guò)程結(jié)束之后，傳播的范圍達(dá)到最大）已被證明是一個(gè)NP-hard問(wèn)題。目前，大多數(shù)的研究尋找度最大的節(jié)點(diǎn)、網(wǎng)絡(luò)關(guān)系中的關(guān)鍵節(jié)點(diǎn)、網(wǎng)絡(luò)中的中心節(jié)點(diǎn)等作為初始節(jié)點(diǎn)，如貪婪算法［6］、k-shell算法等，但是這些都是在傳播網(wǎng)絡(luò)理想化的基礎(chǔ)上。那么以ABM計(jì)算實(shí)驗(yàn)?zāi)Ｐ偷幕A(chǔ)上，該如何選擇初始節(jié)點(diǎn)才能使傳播效果最大化理想化？

2.1度最大的節(jié)點(diǎn)

擁有較多鄰居的節(jié)點(diǎn)能夠?qū)⑿畔鞑サ礁嗟木W(wǎng)絡(luò)中的其他節(jié)點(diǎn)。在一個(gè)社會(huì)網(wǎng)絡(luò)中，某節(jié)點(diǎn)度數(shù)最高，該點(diǎn)就居于中心位置，即該點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)為此網(wǎng)絡(luò)中的中心人物即最具影響［7］。圖2是由10個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，灰色節(jié)點(diǎn)擁有最大的度5，顯然該節(jié)點(diǎn)在傳播一步和兩步的情況下，傳播到的節(jié)點(diǎn)數(shù)最多。所以在選擇初始節(jié)點(diǎn)時(shí)，考慮度最大的節(jié)點(diǎn)。

圖2　選擇度最大的節(jié)點(diǎn)

2.2鏈路權(quán)值和最大的節(jié)點(diǎn)

每個(gè)人認(rèn)識(shí)的人就是度，但一般情況下只與關(guān)系比較密切的人交流。用鏈路權(quán)值來(lái)表示節(jié)點(diǎn)間的親疏關(guān)系。如果不僅考慮節(jié)點(diǎn)的人脈，還考慮節(jié)點(diǎn)的影響力，用0～1之間的數(shù)值代表節(jié)點(diǎn)之間不同的親密程度，連接權(quán)值的和代表了節(jié)點(diǎn)的影響力的大小。如圖3所示，在這種情況下，灰色的節(jié)點(diǎn)就不是最佳的初始節(jié)點(diǎn)，因?yàn)槠滏溌窓?quán)值和只有0.9，相反，淺灰色節(jié)點(diǎn)的鏈路權(quán)值和達(dá)到了1.5，所以淺灰色的節(jié)點(diǎn)是最佳的初始節(jié)點(diǎn)。

圖3　鏈路權(quán)值和最大的節(jié)點(diǎn)

2.3屬性值最佳的節(jié)點(diǎn)

社會(huì)個(gè)體財(cái)富、性格、社會(huì)地位等方面都各不相同，而這些屬性也影響了個(gè)體的重要性。如果要傳播的是一個(gè)理財(cái)產(chǎn)品的信息，那么財(cái)富值低的節(jié)點(diǎn)可能會(huì)對(duì)這個(gè)信息做丟棄處理。如圖4所示，在這種情況下，淺灰色的節(jié)點(diǎn)可能就是最佳的初始點(diǎn)。

圖4　屬性值最佳的節(jié)點(diǎn)

2.4基于ABM的初始節(jié)點(diǎn)選擇

由前文可知，節(jié)點(diǎn)的度、鏈路權(quán)值和以及屬性值都會(huì)影響節(jié)點(diǎn)的重要性，所以選擇初始節(jié)點(diǎn)時(shí)需要綜合考慮這三個(gè)方面的因素，即Q=a×Degree+b×Link+（1-a-b）×Attribute，其中Degree代表節(jié)點(diǎn)度，Link代表鏈路權(quán)值和，Attribute代表屬性值。Q值最大的節(jié)點(diǎn)作為初始節(jié)點(diǎn)的傳播效果會(huì)更好，而Q值受a和b的影響，不同的信息傳播模型有不同的最佳a(bǔ)、b值。通過(guò)綜合三方面因素，可以找出最佳的初始節(jié)點(diǎn)。

3　仿真模型及結(jié)果

仿真模型包括社會(huì)網(wǎng)絡(luò)的模擬構(gòu)建、網(wǎng)絡(luò)節(jié)點(diǎn)的異構(gòu)性設(shè)置、信息的傳播。本文基于無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)建社會(huì)網(wǎng)絡(luò)，即節(jié)點(diǎn)度服從冪次分布。為了簡(jiǎn)化模型，只設(shè)置了單個(gè)節(jié)點(diǎn)屬性財(cái)富值，服從標(biāo)準(zhǔn)正態(tài)分布。模型傳播一條理財(cái)產(chǎn)品信息，節(jié)點(diǎn)進(jìn)行接收、處理、決定。節(jié)點(diǎn)接收信息后根據(jù)自身的財(cái)富值來(lái)判斷對(duì)該信息的興趣度，人們一般選擇與自己親密度較高的個(gè)體即與自己連接強(qiáng)度大的鄰居。網(wǎng)絡(luò)、節(jié)點(diǎn)、信息以及節(jié)點(diǎn)的行為規(guī)則構(gòu)成了基于ABM的信息傳播模型。

圖5顯示了信息傳播比例變化，整體上傳播比例隨著時(shí)間步先緩慢上升，在中間有一個(gè)快速上升躍變的過(guò)程后趨于緩慢變化，整體呈現(xiàn)“S”形，與ROGERS E M的創(chuàng)新采納比例變化趨勢(shì)相吻合。第1條曲線選擇了鏈路權(quán)值和前5%的節(jié)點(diǎn)為初始節(jié)點(diǎn)，第2條為節(jié)點(diǎn)屬性值前5%，第3條為節(jié)點(diǎn)的度前5%，第4條為Q值前5%，其中a=b=1-a-b。從圖中可以看到，以鏈路權(quán)值和來(lái)選擇效果最差，以屬性值來(lái)選擇效果中等，而以度和Q值來(lái)選擇效果較好。以Q值來(lái)選擇的傳播效果雖然在起步階段沒(méi)有以度來(lái)選擇的傳播效果好，但是其“S”形上升階段更陡峭，最后達(dá)到的傳播比例更大。所以綜合考慮三個(gè)方面的Q值更適合用于選擇合適的初始節(jié)點(diǎn)。

圖5　實(shí)驗(yàn)結(jié)果圖

4　結(jié)論

本文研究了基于ABM的信息傳播下代理在信息傳播中的行為。在無(wú)標(biāo)度網(wǎng)絡(luò)的社會(huì)網(wǎng)絡(luò)模型中定義了代理的屬性和行為。在達(dá)到傳播效果最大化問(wèn)題上，本文考慮了除網(wǎng)絡(luò)結(jié)構(gòu)之外的其他因素，并在基于ABM的信息傳播模型上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)表明，在選擇初始節(jié)點(diǎn)時(shí)考慮除網(wǎng)絡(luò)結(jié)構(gòu)以外的因素，能夠使傳播效果更好、更快。

［1］FOURT L A，WOODLOCK JW.Early prediction of market success for new grocery products［J］.Journal of Marketing，1960，25：31-38.

［2］MANSFIELE E.Technical change and the rate of initation［J］. Econometrica，1961，29（4）：741-766

［3］BASS F M.A new product growth for model consumer durables［J］.Management Science，1969，15（2）：215-227.

［4］BANERJEE A，CHANDRASEKHAR A G，DUFLO E，et al. The diffusion ofmicrofinance［J］.Science，2013，341：363-370.

［5］ROGERS E M.Diffusion of innovations（5th edition）［M］.New York：Free Press，2003.

［6］Chen Wei，Wang Yajun，Yang Siyu.Efficient influence maximization in social networks［C］.Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Paris，F(xiàn)rance，2009：199-208.

［7］Lin Juren.Social network analysis：theory，methods and applications［M］.Beijing：Beijing NormalUniversity Press，2009.

林慧嫻（1991-），碩士研究生，主要研究方向：社會(huì)網(wǎng)絡(luò)及基于代理的建模方法。

陸靜曄（1990-），碩士研究生，主要研究方向：社會(huì)網(wǎng)絡(luò)及基于代理的建模方法。

Initial nodes selection in agent-based information diffusion model

Lin Huixian，Lu Jingye
（College of Telecommunications&Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

How to choose initial nodes to maximum the range of transmission has

wide attention.but most of the study is limited to the network structure，ignoring the heterogeneity of nodes.We construct an information transmission model which consists of nodes with heterogeneous attributes and behaviors based on the ABM，and discuss the importance of different factors.The experiment results show that it′s more effective in finding the most influential nodes when taking network structure and nodes heterogeneity into consideration.

social network；information diffusion；agent；node selection

TP399

A

1674-7720（2015）04-0055-03

（2014-10-15）