陸斌斌

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

社交網(wǎng)絡(luò)中話題傳播結(jié)構(gòu)的可視化研究與實(shí)現(xiàn)

陸斌斌

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

以新浪微博為例，以話題為信息傳播研究的基本單位，分析信息的傳播路徑，提出話題信息傳播網(wǎng)絡(luò)構(gòu)建算法，實(shí)現(xiàn)話題傳播結(jié)構(gòu)可視化分析系統(tǒng)，并對(duì)可視化布局進(jìn)行優(yōu)化。

話題傳播；可視化；網(wǎng)絡(luò)結(jié)構(gòu)；網(wǎng)絡(luò)布局

0 引言

移動(dòng)通信網(wǎng)絡(luò)已擁有4G技術(shù)的帶寬，智能移動(dòng)終端也達(dá)到了較高的保有量，社交網(wǎng)絡(luò)平臺(tái)順勢(shì)以前所未有的深度和廣度滲入人類的生活。例如國(guó)內(nèi)社交網(wǎng)絡(luò)平臺(tái)新浪微博，其注冊(cè)用戶已就經(jīng)超過了6億，用戶活躍度的增長(zhǎng)也呈現(xiàn)出抬頭的趨勢(shì)。人們進(jìn)行信息傳遞的方式因此也發(fā)生著巨變，社交網(wǎng)絡(luò)中的每一個(gè)獨(dú)立個(gè)體都可以通過這個(gè)平臺(tái)隨時(shí)隨地接收、生產(chǎn)和傳遞信息。隨之產(chǎn)生的通信數(shù)據(jù)潛藏了社會(huì)活動(dòng)規(guī)律和人們的行為模式，研究人員可以通過這些規(guī)律和模式探索信息在社交網(wǎng)絡(luò)中的傳播擴(kuò)散情況，輔助社會(huì)科學(xué)的研究與應(yīng)用。而且由于在線社會(huì)網(wǎng)絡(luò)與其用戶在線下真實(shí)世界中組成的社會(huì)網(wǎng)絡(luò)是相互映射相互影響的，通過研究在線社會(huì)網(wǎng)路中的信息傳播問題，還可以幫助研究者進(jìn)行線下不易開展的研究活動(dòng)。

然而大規(guī)模的微博流卻給研究者們帶來了挑戰(zhàn)：社會(huì)科學(xué)研究者在研究社會(huì)網(wǎng)絡(luò)時(shí)，多使用的是類似于問卷調(diào)查的方式采集真實(shí)社會(huì)中的數(shù)據(jù)，非常麻煩耗時(shí)。所以社會(huì)科學(xué)家在分析社會(huì)網(wǎng)絡(luò)時(shí)通常處理的數(shù)據(jù)集都很小，分析方法也大多是統(tǒng)計(jì)學(xué)方法[1]，無法很好地運(yùn)用大規(guī)模的在線社交網(wǎng)絡(luò)通信數(shù)據(jù)。與此同時(shí)，計(jì)算機(jī)科學(xué)研究者使用社交網(wǎng)絡(luò)的通信數(shù)據(jù)研究社會(huì)網(wǎng)絡(luò)時(shí)也面臨著困境，他們?cè)谑褂糜?jì)算機(jī)技術(shù)進(jìn)行大規(guī)模數(shù)據(jù)的收集、存儲(chǔ)、過濾和分析時(shí)，都需要學(xué)習(xí)社會(huì)科學(xué)相關(guān)領(lǐng)域的知識(shí)，然而學(xué)習(xí)的過程通常是相當(dāng)耗時(shí)且較為昂貴的。

運(yùn)用可視化技術(shù)[2-3]研究社會(huì)網(wǎng)絡(luò)中的大規(guī)模數(shù)據(jù)為以上問題提供了有效的解決方法，它主要用于微博數(shù)據(jù)流這樣的大規(guī)模非數(shù)值型數(shù)據(jù)，將源數(shù)據(jù)轉(zhuǎn)化為簡(jiǎn)潔易懂符合人們認(rèn)知習(xí)慣的的視覺圖像信息。既為研究者解決了數(shù)據(jù)量大所帶來的研究難度，又免去了許多社會(huì)科學(xué)背景知識(shí)的學(xué)習(xí)。本文通過有效算法構(gòu)建信息傳播網(wǎng)絡(luò)并利用可視化分析方法對(duì)信息傳播模式進(jìn)行了探索。

1 話題信息傳播網(wǎng)絡(luò)構(gòu)建算法

話題傳播結(jié)構(gòu)可以以圖（Graph）結(jié)構(gòu)的形式進(jìn)行描述。圖由頂點(diǎn)（Vertex）和邊（Edge）兩個(gè)有限集合組成，形式化定義為Graph=（V，E），其中V稱為頂點(diǎn)集，V中的每一個(gè)頂點(diǎn)對(duì)應(yīng)于話題傳播網(wǎng)絡(luò)中的一個(gè)用戶；E={|P（u，v）∧（u，v∈V）}，其中頂點(diǎn)對(duì)稱為邊，對(duì)應(yīng)于話題傳播網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)或評(píng)論。此算法有兩個(gè)前提：（1）假設(shè)轉(zhuǎn)發(fā)列表中的所有元素都是按照時(shí)間順序排列的。（2）不考慮同一個(gè)用戶換發(fā)來自不同用戶的同一條微博的情況（事實(shí)上這樣的情況在真實(shí)世界中對(duì)信息傳播的作用確實(shí)可以忽略不計(jì)）。

話題傳播網(wǎng)絡(luò)的構(gòu)建過程通過以下算法詳細(xì)描述：

2 話題傳播結(jié)構(gòu)可視化

話題傳播網(wǎng)絡(luò)構(gòu)建完成后，本文采用了基于能量模型的力導(dǎo)引算法對(duì)節(jié)點(diǎn)進(jìn)行布局。FR[4]算法是力導(dǎo)引布局算法的一種實(shí)現(xiàn)版本，它能夠?qū)⒕W(wǎng)絡(luò)中的節(jié)點(diǎn)和邊進(jìn)行均勻的分布，同時(shí)能夠減少邊的交叉。下面的偽代碼是FR布局算法的實(shí)現(xiàn)表示：

在其基礎(chǔ)之上，進(jìn)行三點(diǎn)優(yōu)化：

（1）斥力計(jì)算優(yōu)化：力導(dǎo)引算法計(jì)算斥力時(shí)需要考慮所有節(jié)點(diǎn)之間的相互作用力，時(shí)間復(fù)雜度為O（|V|2），為了減少該時(shí)間復(fù)雜度，對(duì)于兩點(diǎn)之間距離較遠(yuǎn)的點(diǎn)，不作考慮。

（2）邊緣限制：力導(dǎo)引算法不會(huì)限制點(diǎn)的位置范圍，這樣會(huì)導(dǎo)致圖中的節(jié)點(diǎn)位置超過了繪制畫布，造成可視化結(jié)果不全。本論將位置分為水平方向和數(shù)值方向，當(dāng)某一個(gè)方向的位置超過范圍時(shí)，把該方向的坐標(biāo)值設(shè)置為邊緣坐標(biāo)，但另一個(gè)方向依然會(huì)因?yàn)榱Φ淖饔卯a(chǎn)生位移。

（3）中心控制：力導(dǎo)引算法的布局結(jié)果通常為了節(jié)點(diǎn)和邊的對(duì)稱性都會(huì)排布得很均勻，比較靠近中心。然而因?yàn)樗惴ú]有明確地限制節(jié)點(diǎn)在整個(gè)屏幕的整體分布位置，加上所有節(jié)點(diǎn)的初始位置都是隨機(jī)的，所以偶爾會(huì)出現(xiàn)最終的結(jié)果偏離屏幕中心的情況。本文引入了一個(gè)“中心節(jié)點(diǎn)”對(duì)布局結(jié)果的整體位置進(jìn)行中心控制。在屏幕中央有一個(gè)固定不變的點(diǎn)，該點(diǎn)持續(xù)不斷地對(duì)其他節(jié)點(diǎn)產(chǎn)生引力，而引力的大小最終由實(shí)驗(yàn)數(shù)據(jù)和經(jīng)驗(yàn)值確定。

除了布局算法以外，設(shè)計(jì)了具有高分辨度的視覺映射以及靈活的交互方式，最終實(shí)現(xiàn)了面向話題傳播結(jié)構(gòu)的可視化分析系統(tǒng)。可視化效果如圖1所示：

圖1 可視化效果圖

3 結(jié)語

本文針對(duì)國(guó)內(nèi)主流的社交網(wǎng)絡(luò)平臺(tái)——新浪微博，以話題為信息傳播的基本單位，對(duì)信息在社交網(wǎng)絡(luò)中的傳播結(jié)構(gòu)采用可視化手段進(jìn)行了研究。提出了一種話題信息傳播結(jié)構(gòu)的構(gòu)建算算法，實(shí)現(xiàn)了話題傳播結(jié)構(gòu)可視化分析原型系統(tǒng)，并對(duì)布局方法進(jìn)行了優(yōu)化。

[1]Marin A，Wellman B.Social Network Analysis:An Introduction[J].The SAGE Handbook of Social Network Analysis，2011:11-25.

[2]McKelvey K R，Menczer F.Truthy:Enabling the Study of Online Social Networks[C].Proceedings of the 2013 Conference on Computer Supported Cooperative Work Companion.ACM，2013:23-26.

[3]Ren D，Zhang X，Wang Z，et al.Weibo Events:A Crowd Sourcing Weibo Visual Analytic System[C].Pacific Visualization Symposium（PacificVis），2014 IEEE.IEEE，2014:330-334.

[4]Tomas Fruchterman，Edward Reingold.Graph Drawing by Force-Directed Placement[J].Software Practice and Experience，Vol.21，1991.P1129-1164

Research and Implementation of Topic Diffusion Structure Visualization Based on Online Social Network

LU Bin-bin
（College of Computer Science，Sichuan University，Chengdu 610065）

Takes Sina Microblog as an example,proposes a structure-build algorithm for topic diffusion and realizes a visualization system with an improved network layout to analyze propagation path of topic information.

Topic Communication;Visualization;Network Structure;Network Layout

1007-1423（2017）07-0058-04

10.3969/j.issn.1007-1423.2017.07.015

陸斌斌（1991-），男，浙江慈溪人，研究方向?yàn)樾畔⒖梢暬⒖梢暦治?/p>

2017-01-10

2017-03-02