陸斌斌

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

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

陸斌斌

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 可視化效果圖

3 結(jié)語

本文針對國內(nèi)主流的社交網(wǎng)絡(luò)平臺——新浪微博，以話題為信息傳播的基本單位，對信息在社交網(wǎng)絡(luò)中的傳播結(jié)構(gòu)采用可視化手段進(jìn)行了研究。提出了一種話題信息傳播結(jié)構(gòu)的構(gòu)建算算法，實現(xiàn)了話題傳播結(jié)構(gòu)可視化分析原型系統(tǒng)，并對布局方法進(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-），男，浙江慈溪人，研究方向為信息可視化、可視分析

2017-01-10

2017-03-02