面向社交媒體嵌入關系數據感知方法的研究

崔穎安,李雪,夏輝,張德運

(1.西安理工大學計算機科學與工程學院,710048,西安;2.西安交通大學電子與信息工程學院,710049,西安;3.陜西師范大學國際商學院,710062,西安)

?

面向社交媒體嵌入關系數據感知方法的研究

崔穎安1,2,李雪3,夏輝1,張德運2

(1.西安理工大學計算機科學與工程學院,710048,西安;2.西安交通大學電子與信息工程學院,710049,西安;3.陜西師范大學國際商學院,710062,西安)

針對社交媒體數據感知成本高、數據感知效率低等問題,提出了社交媒體嵌入關系多階段數據感知方法(online social media-multi stage data aware, OSM-MSDA)。該方法以數據感知對象內部關系的分布特征為基礎,構造一個具有偏好特征的種子網絡;采用Metropolis-Hastings方法優先選取數據感知對象中高度節點的鄰接關系,快速填充特征網絡,實現網絡輪廓探測;使用基于馬爾可夫生滅機制的延遲拒絕方法控制概率轉移核,對局部耦合關系進行修剪,確保連通關系疏密的合理分布。實驗結果表明:OSM-MSDA建立的多階段漸進數據抽樣方法,能夠克服已有數據感知方法采集樣本的盲目性,在宏觀尺度準確、高效的感知社交媒體嵌入關系的社會資本特征,確保特征網絡與數據感知對象的結構更具有一致性,同時還能降低數據的使用成本,將數據處理效率提高32%～63%。

社交媒體;嵌入關系;多階段;數據感知

在組織理論中,社交媒體形成的社會網絡被定義為關系嵌入與結構嵌入。關系嵌入是指個體行動者的行為嵌入于個體行動者彼此之間的互動關系網絡中,通過社會聯結的密度、強度、對稱性等要素對個體行動者的決策產生影響。結構嵌入是指由個體行動者涌現而成的凝聚子群進一步鑲嵌到更大范圍的網絡中,依據其在整體網絡中所處的位置與其他凝聚子群發生聯系,從而促進整體網絡的演進與組織[1-2]。

已有研究表明:社交媒體嵌入關系的形成、演化與應用已成為多個學科共同關注的熱點問題[3-4]。盡管不同學科對于社交媒體的研究主題各不相同,但是這些研究均需使用社交媒體嵌入關系數據作為實證基礎。社交媒體嵌入關系除了具有多樣、快速、靈活、海量的基本特性以外,還有其自身獨有的特點。因此有必要對社交媒體嵌入關系數據感知方法進行專門的研究。

綜合國內外相關研究文獻,現有數據感知方法的研究主要包括以下3類:

(1)人工數據感知方法。由程序開發人員使用通用的編程語言或特別設計的腳本語言,根據每一個網頁的特定結構編寫個性化的數據感知包裝器。由于包裝器的數據感知規則與頁面結構具有同一性,數據感知的質量和效率通常都會比較高。該方法的不足是一旦頁面發生變化,包裝器就失去數據感知能力,需要人工修改,維護成本比較高,不適合大規模商用。

(2)半自動數據感知方法。由于人工構造的數據感知包裝器學習成本與維護成本都比較高,半自動數據感知包裝器就應運而生,該方法需要一定的人工操作,通過數據標注以輔助包裝器的生成。通常這些標注操作都會比較簡單,標注員不需掌握程序設計知識即可完成。常用的半自動數據感知包裝器分為兩類:一類是通過歸納推導構造的包裝器,包括模式規則法和模板樹匹配法;另一類是通過機器學習法構造的包裝器,從網頁的特征數據中訓練出統計模型,實現數據感知與解析。

(3)全自動數據感知方法。不需要用戶參與且不使用人工標注訓練樣本,就能產生數據感知規則的方法統稱為全自動數據感知方法。常用的全自動數據感知包裝器分為3類:①基于本體知識的數據感知包裝器;②基于視覺信息的數據感知包裝器;③基于重復相似子樹識別的數據感知包裝器。以上3類方法都能自適應地調整數據感知規則以適應網頁結構的變化。

1 多階段數據感知方法

1.1 總體框架

現有數據感知方法用于社交媒體時,還存在數據感知效率低、成本高、規模難以控制等不足,因此本文提出多階段社交媒體嵌入關系數據感知方法(online social media-multi stage data aware, OSM-MSDA)。該方法的基本思想是以逐步求精的方式,通過合理控制數據感知的規模,構造一個與數據感知對象具有相同社會資本特征的特征網絡。該方法由種子網絡初始化、網絡輪廓探測、局部關系修剪3部分構成。種子網絡初始化使用領域問題研究者提供的初始節點作為種子,以數據感知對象內部的關系為基礎,采用加點、加邊和重連的方法構造一個既具有偏好連接特征也具有隨機性的種子網絡。網絡輪廓探測使用改進的“滾雪球”方法從數據感知對象中挑選合適的關系,對種子網絡進行填充,這些新進入的節點與關系與種子網絡中已有的節點組織在一起,形成數據感知對象的整體輪廓。局部關系修剪使用基于生滅鏈機制的Delay Rejection方法對數據感知對象中對應的局部關系進行篩選,調整不同節點之間關系分布的密度,確保特征網絡與數據感知對象在細節上更具一致性。

1.2 OSM-MSDA算法過程

1.2.1 種子網絡初始化 本文采用偏好隨機網絡法構造種子網絡,該方法的工作過程如下。

(1)初始化種子。從數據感知對象中等概率的選取n個節點,m條邊放入特征網絡中構造初始種子網絡G,令p、q、1-p-q分別代表加點、加邊和重連的概率。

(2)加點。從數據感知對象中隨機的選擇一個新節點添加到特征網絡G中,若該節點的度是ki,采用式(1)的概率分布規則與數據感知對象中的節點相連,α為[0,1]之間的任意隨機數。

p(ki,α)=∑u∈Aiki+α/∑u∈V(ki+α)

(1)

(3)加邊。在數據感知對象中隨機選擇l條邊,這些邊按照式(1)的概率分布規則連接到特征網絡對應的關系中。如果特征網絡缺少數據感知對象中對應的節點,需要補充相應節點構成對應的關系。

(4)重連。在種子網絡中,隨機選取任意一個節點i,刪除該節點所有的關系,而后按照式(1)進行關系重連。特征網絡關系的選取仍需以數據感知對象為基準,而后在特征網絡內選取與之對應的關系進行關系重構。

使用上述方法構造的種子網絡具有以下演化特性:式(2)表示增加一個度為s的節點的演化規律,式(3)表示增加l條邊的演化規律,式(4)表示重連l條邊的演化規律。

(2)

(3)

(4)

由上述方程,可得種子網絡節點度的演化方程為

(5)

對演化方程求解得

(6)

A=(1-p-q)m+a+

(7)

(8)

若加點、加邊與重連在時間t內以等概率方式發生,則節點度的概率分布函數為

(9)

對其求期望可得

(10)

由式(10)可知節點度的期望γ∈[2,3],該值表明種子網絡的度分布符合冪律分布,由此可知種子網絡內部的關系具有偏好連接特征。

1.2.2 網絡輪廓探測 本文采用改進的“滾雪球”方法進行網絡輪廓探測,該方法的工作過程如下。

(1)在種子網路中隨機選取任一節點作為初始的“雪球”。使用Metropolis-Hastings抽樣方法[5]在數據感知對象中抽選與之對應節點的相鄰節點填充種子網絡。

(2)Metropolis-Hastings算法需要構造一個具有平穩性的Markov鏈。為了實現這一目標,需要借助分布函數q(x)來控制樣本點選取。工作過程為:

步驟1 使用提議函數產生新的候選樣本;

步驟2 依據式(11)計算樣本接受概率,其中Λ為二者中較小的值

(11)

步驟3 以概率A(X(t),Y1)接受新樣本或者以概率1-A(X(t),Y1)保持原來的樣本。

Metropolis-Hastings方法非常健壯,本文使用種子網絡中的度分布構造概率密度函數π(X(t)),使用數據感知對象中相鄰節點之間的度分布比值構造q(X(t),Y1)。Metropolis-Hastings抽樣過程如圖1所示。

(3)如果入選節點與種子網絡中其他節點也存在相鄰關系,則在種子網絡中補充對應關系,而后繼續在數據感知對象中尋找合適的節點。

(a)步驟1 (b)步驟2

(c)步驟3 (d)步驟4圖1 網絡輪廓探測中節點關系變化

1.2.3 局部關系修剪 本文使用Delayed-Rejection(DR)方法進行局部關系修剪,該方法的工作過程如下[6-7]。

(1)在種子網絡中隨機選取任一節點作為初始節點。

(2)使用不等概控制方法(如式(13))作為第一層提議函數抽選與之對應節點的相鄰節點。如果候選節點選擇有效,則將其填充到特征網絡中;若無效,將該節點暫時保留到棧中。

(13)

(3)將舍棄的節點從棧中取出,使用生滅鏈提議函數作為第二層提議函數,探索該節點的相鄰關系,若相鄰關系有效,則將其放入特征網絡,反之則徹底舍棄該節點。

(4)重復以上過程,直至收斂到平穩分布。

將生滅鏈方法用于局部關系修剪時,需要知道概率密度函數、提議分布、生滅鏈狀態選擇函數以及由此而生的雅克比行列式。通常情況下,獲得以上計算要素需進行貝葉斯學習。為了提高效率,本文采用其他方法解決以上問題。

就社交媒體嵌入關系這一特定數據感知對象而言,經過種子網絡初始化與網絡輪廓探測以后,可以認為特征網絡與數據感知對象具有較高的相似性,因此可以使用特征網絡的數據近似替代數據感知對象。

另外,MCMC方法有一個非常重要的特性:“提議函數的選取只影響收斂速度,不會影響馬爾科夫鏈最終的收斂”[8]。因此可以從最“悲觀”的情況出發,選擇沒有穩定期望的柯西分布作為基本提議函數。為了提高提議分布向真實分布逼近的效率,增加樣本點與其相繼關系的出度比作為柯西分布的修正參數。

對于生滅鏈轉換函數,可以選擇正態分布作為生滅鏈轉換函數。正態分布的中心區域代表更新狀態,正態分布的兩端分別代表死亡和新生的概率(例如生、滅各為7%,更新為86%)。綜合基本提議函數、生滅鏈轉換函數以及修正參數共同組成新提議分布。在明確了提議分布以后,雅克比矩陣的計算就非常簡單,可由柯西分布和正態分布共同給出。

局部關系修剪中“節點出生”對抽樣關系的修正作用如圖2所示。在原網絡中,圖2a所示兩個子網之間的有向相干關系分別是2條關系(由左向右)和3條關系(由右向左),但是經過網絡輪廓探測以后,由左向右的連通關系丟失。使用生滅鏈方法時,假設選中節點a,若此時處于“節點出生”狀態,則在數據感知對象中,選中a的相鄰節點b,而后根據公式(14)選擇其相鄰關系(假設c被選中),則b→c關系被選中,將其放入特征網絡中以彌補網絡輪廓探測的不足。“節點死亡”與“節點出生”相似,是上述過程的逆過程。

(a)原網絡

(b)網絡輪廓探測后關系失衡

(c)“節點出生”的修正圖2 馬爾科夫鏈節點出生變化示意圖

2 測試數據集

本文選擇新浪微博、蘑菇街、土豆視頻、瑞麗作為測試對象。選擇以上社交媒體的主要原因是:①系統運營時間長,用戶行為趨于穩定,具有研究的穩定性基礎;②數據規模龐大,特征網絡與數據感知對象對比效果明顯;③內部結構復雜,具有測試典型性。測試數據的基本特征如表1所示。

3 數據感知質量分析

3.1 質量特性分析

從整體網絡特性、凝聚子群特性、關鍵節點地位3個維度對特征網絡與總體數據集進行比較分析。

表1 測試數據集

使用OSM-MSDA完成數據感知以后,首先需要對特征網絡與總體數據的擬合優度進行單樣本假設檢驗。假設檢驗的真命題是特征網絡與數據感知對象的分布具有一致性,假命題是特征網絡與數據感知對象的分布不具有一致性。令顯著性水平α=0.1,表2與表3的假設檢驗結果說明命題真命題是假設成立,表明特征網絡與數據感知對象已具有一致性,特征網絡數據具有較高的信度和效度。

表2 OSM-MSDA宏觀特性假設檢驗

對采集的數據感知對象總體做進一步的分析,可以發現土豆網的特點是網絡規模大,但是其中的孤立點很多(約35%),缺少明星節點,整體結構類似于隨機網絡。瑞麗網的特點是網絡規模小,有少量的高度節點(約8%),高度節點的入度雖然較高,但是無標度性不突出,另外低度節點之間的聯系很少,整體網絡類似若干個小型星型網絡組成的復合體。蘑菇街的特點是網絡規模大,有一部分高度節點(約13%),高度節點之間缺少聯系,但是低度節點之間聯系比較豐富,整體結構類似于小世界網絡組成的復合體。新浪微博的特點是網絡規模非常大,內部結構非常復雜,無標度性、小世界性、隨機性都比較明顯,是典型的混合網絡。

表3 OSM-MSDA凝聚子群特性K-S檢驗

表3給出了特征網絡與數據感知對象成分的K-S檢驗結果(如果一個圖可以分為多個子圖,每個子圖內部成員之間有聯系,但是不同子圖之間沒有任何聯系,這樣的子圖被稱為成分),表中K-S檢驗結果(除新浪微博1個指標以外),均能滿足顯著性水平檢驗的要求,表明OSM-MSDA對凝聚子群的數據感知效果比較好。另外從表3可以看出,內部結構越簡單的社交媒體,其假設檢驗效果越好(令假設檢驗結果為I,則I土豆網

綜合表2與表3的數據,可以確定OSM-MSDA對不同類型的社交媒體均表現出較好的數據感知效果。從數據感知的運行過程來看:在種子網絡初始化階段,通過有意的控制,確保低度節點與高度節點都能進入特征網絡,解決了節點的構成復雜性;在網絡輪廓檢測階段,隨著高度節點的相鄰關系不斷進入特征網絡,這些樣本組織在一起形成多個凝聚子群,解決了節點關系的拓撲復雜性;在局部關系修剪階段,使用延遲拒絕方法有效的選擇低度節點,而后通過馬爾科夫生滅鏈機制調整局部關系分布的密度,形成更大的子群以及整體網絡。

表4是關鍵節點的地位關系,表中數據采用皮爾森相關系數對排名前0.1%高入度與高出度行動者進行了規則相關性分析,根據相關程度將其均分為4檔。從表4中對關鍵節點地位相似性的K-S檢驗來看,特征網絡中高度節點的相似性與真實網絡中差異較大,這說明OSM-MSDA方法對高度節點關系的數據感知效果存在不足。針對此問題,可以采取擴大樣本規模或者使用協方差矩陣構造自適應局部關系分布特征估計函數來優化高度節點的選取。

表4 關鍵節點相似性K-S檢驗 %

3.2 性能特性分析

圖3給出了使用特征網絡與總體數據進行社會網絡分析耗費時間的對比數據,比較結果顯示使用特征網絡的分析效率明顯優于總體數據,這為領域問題的研究帶來了很多方便。事實上,由于社交媒體嵌入關系數據的規模過于龐大(例如新浪微博),使得分析周期過長,就會帶來數據分析結果與社交媒體嵌入關系演化不同步的問題,這樣的結果對實際工作的參考價值就很有限,甚至有可能出現誤導。

圖3 特征網絡與總體數據分析效率對比

4 結 論

本文圍繞著總體數據未知,又要快速、低成本地進行社交媒體嵌入關系數據感知這一問題展開了3個方面的研究工作。首先對現有數據感知方法進行了分析,指出現有數據感知方法存在的問題;而后提出了多階段數據感知方法。通過種子網絡初始化、網絡輪廓探測與局部關系的修剪快速構造了一個與數據感知對象具有較高相似度的特征網絡;最后以真實的社交媒體為研究對象,進行了實際測試,測試結果表明OSM-MSDA方法具有較好的可用性,能夠低成本、高性能為研究者獲取社交媒體大數據。

[1] ROOKS G, SNIJDERS C, DUYSTERS G. Ties that tear apart: the social embeddedness of strategic alliance termination [J]. The Social Science Journal, 2013, 50(3): 359-366.

[2] BHARADWAJ A, EL SAWY O A, PAVLOU P A, et al. Digital business strategy: toward a next generation of insights [J]. MIS Quarterly, 2013, 37(2): 471-482.

[3] KITCHIN R. Big data and human geography opportunities, challenges and risks [J]. Dialogues in Human Geography, 2013, 3(3): 262-265.

[4] BESKOS A, CRISAN D, JASRA A. On the stability of sequential Monte Carlo methods in high dimensions [J]. The Annals of Applied Probability, 2014, 24(4): 1396-1445.

[5] MIRA A. On Metropolis-Hastings algorithms with delayed rejection [J]. The American Statistician, 2001, 59(3/4): 231-241.

[6] GREEN P J, MIRA A. Delayed rejection in reversible jump Metropolis-Hastings [J]. Biometrika, 2001, 88(4): 1035-1053.

[7] COTTER S L, ROBERTS G O, STUART A M, et al. MCMC methods for functions: modifying old algorithms to make them faster [J]. Statistical Science, 2013, 28(3): 424-446.

[8] LOVASZ L. Random walks on graphs: a survey [J]. Stochastic processes and their applications, 1974, 2(4): 311-336.

[本刊相關文獻鏈接]

李建東,鄭杰,劉勤,等.異構協作網絡中采用令牌漏桶的多接入業務分配算法.2014,48(8):7-11.[doi:10.7652/xjtuxb 201408002]

安健,桂小林,張進,等.面向物聯網移動感知的服務節點發現算法.2011,45(12):6-9.[doi:10.7652/xjtuxb201112002]

楊軍,張德運.非均勻分簇的無線傳感器網絡數據傳送機制.2009,43(4):14-17.[doi:10.7652/xjtuxb200904004]

許學斌,張德運,張新曼,等.基于特征層和二代曲波變換的多模生物特征融合識別方法.2009,43(10):32-36.[doi:10.7652/xjtuxb200910007]

王晨旭,秦濤,管曉宏,等.有向網絡興趣社區的快速挖掘算法及其在僵尸粉檢測中的應用.2014,48(6):7-12.[doi:10.7652/xjtuxb201406002]

葉娜,趙銀亮,邊根慶,等.模式無關的社交網絡用戶識別算法.2013,47(12):19-25.[doi:10.7652/xjtuxb201312004]

張賽,徐恪,李海濤.微博類社交網絡中信息傳播的測量與分析.2013,47(2):124-130.[doi:10.7652/xjtuxb201302021]

陳國強,王宇平.采用離散粒子群算法的復雜網絡重疊社團檢測.2013,47(1):107-113.[doi:10.7652/xjtuxb201301021]

(編輯 武紅江)

A Research on the Data Aware Method for Social Media with Embedding Relationship

CUI Ying’an1,2,LI Xue3,XIA Hui1,ZHANG Deyun1

(1. School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China; 2. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 3. Department of International Business, Shaanxi Normal University, Xi’an 710062, China)

A multi stage data-aware method for online social media with embedding relationship (online social media-multi stage data aware, OSM-MSDA) is proposed to solve problems of data aware in online social media, such as poor availability, high business cost, and low-efficiency, et al. A seed network with preference characteristics is constructed, and then the Metropolis-Hasting method is used to choose adjacency relation with high degree in data aware population. Finally, the improved Delay-Rejection method is used to regulate the Markov probability transition kernel, and to control the distribution density in local network. Experimental results show that OSM-MSDA gets more precise results for social capital of social media and high-efficiency at macro-level, and overcomes the blindness of existing data aware methods. At the same time, OSM-MSDA ensures the consistency between the characteristics of network and the structure of the data object perception, reduces the cost to use data, and increases the data processing efficiency by 32%-63%.

online social media; embedding relationship; multi-stage; data aware

2014-05-15。

崔穎安(1975—),男,講師。

國家自然科學基金資助項目(71401092,71402144);教育部人文社會科學研究西部和邊疆地區項目(14XJC910002);中央高校基本科研業務費專項資金資助項目(13SZYB01);陜西省社科聯重大理論與現實問題研究基金資助項目(2013C124);陜西省教育廳專項科學研究項目(14JK1545)。

時間:2014-12-11

10.7652/xjtuxb201502006

TP301

A

0253-987X(2015)02-0031-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20141211.0849.001.html