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

林慧嫻，陸靜曄

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

林慧嫻，陸靜曄

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

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

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

0　引言

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

1　ABM計算實驗?zāi)Ｐ图靶畔鞑?/h2>

1.1ABM計算實驗?zāi)Ｐ?/p>

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

圖1　代理的定義

1.2信息傳播

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

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

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

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

2.1度最大的節(jié)點

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5　實驗結(jié)果圖

4　結(jié)論

本文研究了基于ABM的信息傳播下代理在信息傳播中的行為。在無標(biāo)度網(wǎng)絡(luò)的社會網(wǎng)絡(luò)模型中定義了代理的屬性和行為。在達到傳播效果最大化問題上，本文考慮了除網(wǎng)絡(luò)結(jié)構(gòu)之外的其他因素，并在基于ABM的信息傳播模型上進行了實驗。實驗表明，在選擇初始節(jié)點時考慮除網(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-），碩士研究生，主要研究方向：社會網(wǎng)絡(luò)及基于代理的建模方法。

陸靜曄（1990-），碩士研究生，主要研究方向：社會網(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）