基于馬科夫的信息擴(kuò)散模型在社交媒體熱點(diǎn)問(wèn)題中的應(yīng)用

摘要：在大數(shù)據(jù)時(shí)代的今天，如何從海量的社交媒體中尋找信息擴(kuò)散的源頭，并且預(yù)測(cè)信息擴(kuò)散的未來(lái)走勢(shì)，已成為人們非常關(guān)心的熱點(diǎn)問(wèn)題，這就為數(shù)據(jù)挖掘在熱點(diǎn)問(wèn)題上的應(yīng)用提出了新的挑戰(zhàn)。最具影響力信息的挖掘方法有靜態(tài)與動(dòng)態(tài)之分。靜態(tài)方法只是針對(duì)某個(gè)時(shí)間點(diǎn)，有其片面性。動(dòng)態(tài)方法常用的有四種，均有其局限性，用的是最廣的獨(dú)立級(jí)聯(lián)模型與線性閾值模型均需要將激活過(guò)程放置在一個(gè)個(gè)離散的輪回中，是非連續(xù)的。自主研究了一個(gè)基于連續(xù)時(shí)間馬科夫過(guò)程的模型來(lái)模擬現(xiàn)實(shí)世界的信息擴(kuò)散，并根據(jù)每個(gè)節(jié)點(diǎn)擴(kuò)散信息的情況來(lái)預(yù)測(cè)它們?cè)谖磥?lái)的信息擴(kuò)散能力，從而達(dá)到判斷未來(lái)走勢(shì)的目的。

關(guān)鍵詞：馬科夫過(guò)程；信息擴(kuò)散模型；獨(dú)立級(jí)聯(lián)模型；線性閾值模型

一、前言

社交媒體中的一個(gè)重要應(yīng)用就是對(duì)于最具有影響力的用戶(hù)的挖掘[1，2]。這里的影響力可以根據(jù)特定需求擁有不同的定義。第一，我們可以簡(jiǎn)單地將那些擁有最多朋友或者追隨者的用戶(hù)定義為最具影響力的用戶(hù)。最典型的就是那些體育或者娛樂(lè)明星，他們通常擁有極大比例的粉絲或追隨者。第二，針對(duì)社交網(wǎng)絡(luò)中的信息傳播情況來(lái)找出最具影響力的用戶(hù)，例如，如果一個(gè)用戶(hù)的信息經(jīng)常被其他用戶(hù)轉(zhuǎn)發(fā)，我們認(rèn)為這個(gè)用戶(hù)有著比較高的影響力[3]。通常有兩類(lèi)最具影響力用戶(hù)的挖掘方法，一類(lèi)是靜態(tài)方法，另一類(lèi)是動(dòng)態(tài)方法。

二、靜態(tài)挖掘

最簡(jiǎn)單的定義靜態(tài)影響力的方法是社交網(wǎng)絡(luò)圖上的度。例如，根據(jù)朋友關(guān)系得到社交網(wǎng)絡(luò)上的度即是某個(gè)用戶(hù)在網(wǎng)絡(luò)中的朋友數(shù)量，根據(jù)回復(fù)關(guān)系得到的度是某個(gè)用戶(hù)在網(wǎng)絡(luò)中回復(fù)其他用戶(hù)的總數(shù)，根據(jù)傳播關(guān)系得到的度是某個(gè)用戶(hù)所轉(zhuǎn)發(fā)的其他用戶(hù)的總數(shù)，而根據(jù)提及關(guān)系得到的度則是某個(gè)用戶(hù)在網(wǎng)絡(luò)所提及的用戶(hù)的總數(shù)[4]。

和度類(lèi)似的兩種定義用戶(hù)影響力的方法是接近性核心性和中介性核心性。首先，以下公式（1）給出了接近性核心性的定義：

這里U指的是網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，而d指的是兩個(gè)節(jié)點(diǎn)之間的距離。接近性核心性描述了一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中到其他所有節(jié)點(diǎn)的距離。離所有其他節(jié)點(diǎn)越近的節(jié)點(diǎn)，影響力就越大[5]。其次，我們可以在以下公式（2）中找到中介性核心性的定義：

這里的指代從節(jié)點(diǎn)到的最短路徑的數(shù)量，而表示從節(jié)點(diǎn)S到T并且經(jīng)過(guò)v的最短路徑的數(shù)量[6]。中介性核心性描述了某個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中鏈接其他任意兩個(gè)節(jié)點(diǎn)的能力。該能力越強(qiáng)，這個(gè)節(jié)點(diǎn)的影響力越大。

這三種靜態(tài)方法通常假設(shè)社交網(wǎng)絡(luò)是靜態(tài)的，很顯然的是，社交網(wǎng)絡(luò)是處于不停變化中的，因而通過(guò)靜態(tài)方法挖掘到的信息只是針對(duì)某個(gè)時(shí)間點(diǎn)的，是片面的。

三、動(dòng)態(tài)挖掘

為了解決靜態(tài)挖掘方法涉及到的問(wèn)題，將社交網(wǎng)絡(luò)在時(shí)間軸上動(dòng)態(tài)變化的屬性考慮進(jìn)來(lái)，一些動(dòng)態(tài)挖掘用戶(hù)影響力的方法被提了出來(lái)。獨(dú)立級(jí)聯(lián)模型和線性閾值模型都可以被用于衡量用戶(hù)在網(wǎng)絡(luò)中的影響力，從而達(dá)到尋找最具影響力用戶(hù)的目的[7，8]。然而，這些已有的信息擴(kuò)散模型都有它們自身的缺點(diǎn)。（1）它們需要將激活過(guò)程放置在一個(gè)個(gè)離散的輪回中，這樣一來(lái)，對(duì)于一個(gè)特定節(jié)點(diǎn)來(lái)說(shuō)，它就不能在任意時(shí)間點(diǎn)被激活了；（2）部分信息擴(kuò)散模型是描述型模型，而非預(yù)測(cè)型模型。那么，是否存在一種可以克服以上缺點(diǎn)的動(dòng)態(tài)挖掘用戶(hù)影響力的方法呢？為此，本文提出了一個(gè)“基于連續(xù)時(shí)間馬科夫過(guò)程（Continuous-Time Markov Process）的信息擴(kuò)散模型”來(lái)解決上述缺陷。

四、基于連續(xù)時(shí)間馬科夫過(guò)程的信息擴(kuò)散模型

在討論這個(gè)基于連續(xù)時(shí)間的馬科夫過(guò)程的影響力預(yù)知模型之前，先看一下提供挖掘可能的數(shù)據(jù)：時(shí)間影響力社交網(wǎng)絡(luò)。提出這個(gè)網(wǎng)絡(luò)最主要目的就是為了能準(zhǔn)確保留信息在時(shí)間軸上，同時(shí)準(zhǔn)確保留信息在網(wǎng)絡(luò)中的傳播方向。因?yàn)檫@些信息對(duì)于預(yù)知用戶(hù)影響力十分重要。

傳統(tǒng)的社交網(wǎng)絡(luò)可以被表示為，其中v表示社交網(wǎng)絡(luò)中的用戶(hù)，而E表示用戶(hù)之間如何影響。時(shí)間影響力社交網(wǎng)絡(luò)會(huì)考慮到連續(xù)時(shí)間上的信息/主題傳播[9]。在圖1中，我們以3個(gè)主題為例，這3個(gè)主題假定一共有8個(gè)用戶(hù)曾經(jīng)在他們的文章中提到他們，箭頭的指向正是信息傳播的方向。這里，緊跟在每一個(gè)主題之后的是一行傳播該主題的用戶(hù)，而用戶(hù)與用戶(hù)之間的傳播有時(shí)間的延遲，箭頭上的數(shù)字正是他們傳播該信息間隔的時(shí)間。例如，用戶(hù)E和A都提到了主題“iPad”，而用戶(hù)A晚于用戶(hù)E十個(gè)時(shí)間單位提及該主題。假定這樣一個(gè)社交網(wǎng)絡(luò)獲取到之后，下面談一下擬定的基于連續(xù)時(shí)間的馬科夫過(guò)程的影響力預(yù)知模型的建立。

（一）用戶(hù)（節(jié)點(diǎn)）影響力

首先，我們需要定義什么是用戶(hù)影響力。這里，將它定義為一個(gè)用戶(hù)擴(kuò)散一個(gè)主題或信息的能力，給定一個(gè)主題，如果可以讓網(wǎng)絡(luò)中最具影響的用戶(hù)來(lái)發(fā)表這個(gè)主題，我們就有把握讓這個(gè)主題擴(kuò)散到最多的其他用戶(hù)那里。

（二）馬科夫過(guò)程

假設(shè)代表了t時(shí)間點(diǎn)上針對(duì)某一主題/信息的時(shí)間影響力社交網(wǎng)絡(luò)的狀態(tài)。它包含了在時(shí)間點(diǎn)t上發(fā)表關(guān)于該主題文章的用戶(hù)和其他的用戶(hù)。X=X（t），t≥0則構(gòu)成了一個(gè)連續(xù)時(shí)間的馬科夫過(guò)程。在這個(gè)過(guò)程中，一個(gè)用戶(hù)在文章中提及一個(gè)主題的可能性依賴(lài)于這個(gè)主題在整個(gè)歷史上傳播的情況，這個(gè)可能性事實(shí)上僅僅依賴(lài)于在歷史上最近的提及此主題的用戶(hù)。這樣的性質(zhì)即是所謂的馬科夫?qū)傩?，可以由如下公式定義：

這里，是在時(shí)間內(nèi)從用戶(hù)i到j(luò)的傳遞概率?？梢詫看做當(dāng)前討論該主題的用戶(hù)，而j則是緊接著i的下一個(gè)將要討論該主題的用戶(hù)。代表著先于時(shí)間點(diǎn)的主題傳播的歷史。我們假設(shè)傳遞概率并不依賴(lài)于整個(gè)主題傳播過(guò)程的真正起始時(shí)間，那么基于連續(xù)時(shí)間的馬科夫過(guò)程的影響力預(yù)知模型就是時(shí)間齊次的了，公式（3）可改寫(xiě)為：

（三）基于馬科夫過(guò)程的用戶(hù)影響力定義

給定時(shí)間窗口t，為了能夠估計(jì)某一用戶(hù)i在t中的主題擴(kuò)散能力，需要計(jì)算或者估計(jì)該用戶(hù)i到其他所有用戶(hù)的傳遞概率，或者說(shuō)擴(kuò)散概率。有了這個(gè)概率，才能最終預(yù)測(cè)該用戶(hù)可以將主題推廣到多少其他用戶(hù)。對(duì)于用戶(hù)i而言，它在時(shí)間窗口t中的最終推廣數(shù)量可以由如下公式來(lái)定義：

這里，代表了用戶(hù)t在時(shí)間窗口t中可能出現(xiàn)的次數(shù)。這個(gè)參數(shù)可以簡(jiǎn)單地使用根據(jù)窗口t線性遞增估計(jì)的辦法來(lái)得到，同時(shí)，也可以根據(jù)用戶(hù)i在歷史上不同大小的時(shí)間窗口的出現(xiàn)次數(shù)來(lái)使用回歸模型計(jì)算得到。然而，給定任意無(wú)限種可能性的t，估計(jì)傳遞概率P（t）是不現(xiàn)實(shí)的。因此，需要首先計(jì)算傳遞速率矩陣，然后通過(guò)傳遞速率矩陣來(lái)估計(jì)傳遞概率P（t）。

（四）傳遞速率矩陣的計(jì)算

傳遞速率矩陣用Q來(lái)表示，這里稱(chēng)為連續(xù)時(shí)間馬科夫過(guò)程的無(wú)窮小生成元。它被定義為t無(wú)限逼近于P（t）時(shí)的導(dǎo)數(shù)，用如下公式來(lái)定義：

在Q中，每一個(gè)條目qij都指代將一個(gè)主題或者信息從用戶(hù)i傳遞到用戶(hù)j的速率，的每一行的和都是0，而每一行均滿足下式：

qij反映了從用戶(hù)i到用戶(hù)j的傳遞概率的變化。qi是一個(gè)與-qii相等的參數(shù)，指代了用戶(hù)傳遞任意主題到任何其他用戶(hù)的概率。qi的計(jì)算將會(huì)幫助我們計(jì)算其他的參數(shù)。因此，為了能夠計(jì)算qi，我們假設(shè)用戶(hù)傳遞一個(gè)主題到所有其他用戶(hù)的時(shí)間服從一個(gè)指數(shù)分布，該指數(shù)分布的速率參數(shù)正是qi[10]。一個(gè)服從指數(shù)分布的隨機(jī)變量Ti（Ti指代用戶(hù)i傳遞主題的時(shí)間）的期望值可由如下公式給出：

根據(jù)連續(xù)時(shí)間馬科夫過(guò)程的理論，用戶(hù)i傳遞到用戶(hù)j的傳遞速率可以用如下公式估計(jì)：

m代表歷史上從用戶(hù)i傳遞到用戶(hù)j的主題的數(shù)量，而表示第m個(gè)主題從用戶(hù)i到用戶(hù)j的傳遞時(shí)間。

（五）傳遞概率矩陣的計(jì)算

在獲得了Q矩陣后，便可以通過(guò)Q獲取傳遞概率矩陣P（t）。根據(jù)柯?tīng)柲缏宸蛳蚝蠓匠蹋?/p>

通過(guò)代數(shù)變換，以上的公式可轉(zhuǎn)化為：

而這一方程的一般解法是由如下公式給出的：

P（t）是一個(gè)不可約的隨機(jī)矩陣，可以使用泰勒擴(kuò)展來(lái)近似它。P（t）可用如下公式估計(jì)：

這里將的指數(shù)升至一個(gè)足夠大的n 。

得到P（t）矩陣后，然后根據(jù)影響力排序，最終能夠獲得最具影響力的用戶(hù)。

五、預(yù)測(cè)結(jié)果

為了檢驗(yàn)新提出的模型擁有預(yù)測(cè)用戶(hù)影響力的能力，我們將該模型（IDM-CTMP）、真實(shí)的數(shù)據(jù)結(jié)果（Ground Truth）、兩個(gè)基準(zhǔn)模型（差分自回歸滑動(dòng)平均模型（ARIMA）[11]和獨(dú)立級(jí)聯(lián)模型（IC））共四個(gè)模型進(jìn)行對(duì)比，并抽取排名最高的五個(gè)用戶(hù)和隨機(jī)的五個(gè)用戶(hù)進(jìn)行結(jié)果對(duì)比。一共獲取了22天的Twitter數(shù)據(jù)，并利用前12天的數(shù)據(jù)對(duì)兩個(gè)基準(zhǔn)模型和我們提出的模型進(jìn)行建模。然后將后10天的數(shù)據(jù)用于抽取真實(shí)結(jié)果以及模型驗(yàn)證。真實(shí)的數(shù)據(jù)結(jié)果即是用戶(hù)在后10天的數(shù)據(jù)當(dāng)中所傳遞到其他用戶(hù)數(shù)量。

從實(shí)驗(yàn)中得出，盡管新提出的模型無(wú)法完全匹配真實(shí)的結(jié)果，但是大部分的預(yù)測(cè)曲線已經(jīng)與真實(shí)的曲線非常接近了。特別要指出的是，大部分的“峰”（最大值）和“谷”（最小值）都可以被新模型預(yù)測(cè)到。相反，ARIMA和獨(dú)立級(jí)聯(lián)模型做得并不好，錯(cuò)過(guò)了很多真實(shí)的“峰”和“谷”。

六、結(jié)語(yǔ)

論文研究的基于馬科夫過(guò)程信息擴(kuò)散型，對(duì)核心節(jié)點(diǎn)在信息傳播中所起到的作用方面，起到了一定功效，后續(xù)將進(jìn)一步研究社交媒體的其他方面數(shù)據(jù)挖掘，比如社交用戶(hù)的個(gè)性化搜索與海量數(shù)據(jù)社交搜索等。

參考文獻(xiàn)

[1]肖宇，許煒，張晨，等.社交網(wǎng)絡(luò)中用戶(hù)區(qū)域影響力評(píng)估算法研究[J].微電子學(xué)與計(jì)算機(jī)，2012，29（7）：58-63.

[2]王晰巍，賈若男，韋雅楠，等.多維度社交網(wǎng)絡(luò)輿情用戶(hù)群體聚類(lèi)分析方法研究[J].數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn)，2021，5（6）：25-35.

[3]柳向東，曹雨婷，李利梅.網(wǎng)絡(luò)影響力預(yù)知模型：一種大數(shù)據(jù)下高校輿情監(jiān)測(cè)與預(yù)警機(jī)制[J].深圳大學(xué)學(xué)報(bào)（人文社會(huì)科學(xué)版，2015（4）：156-160.

[4]何川.復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)排序算法若干問(wèn)題研究[D].合肥工業(yè)大學(xué)，2018.

[5]張?jiān)茓?社交網(wǎng)絡(luò)個(gè)體影響力模型及其應(yīng)用[D].西南財(cái)經(jīng)大學(xué)，2017.

[6]任留名.基于社會(huì)特性的社交網(wǎng)絡(luò)影響力分析[D]. 合肥工業(yè)大學(xué)，2016.

[7]K.Saito， M.Kimura， K.Ohara， and H.Motoda. Efficient estimation of cumulative influence for multiple activation information diffusion model with continuous time delay[J]. In PRICAI 2010：Trends in Artificial Intelligence， Springer， 2010（6230）：244-255.

[8]K.Saito， M.Kimura， K.Ohara， and H.Motoda. Generative models of information diffusion with asynchronous time delay[C]. In Proceedings of the 2nd Asian Conference on Machine Learning（ACML2010）， 2010：193-208.

[9]曲賢菲，田朝霞，陳旭.基于Motif的社交網(wǎng)絡(luò)用戶(hù)影響力排序方法研究[J].計(jì)算機(jī)科學(xué)與應(yīng)用，2020，10（6）： 1098-1112

[10]X.Song， Y.Chi，K.Hino，and B.L.Tseng. Information flow modeling based on diffusion rate for prediction and ranking. In Proceedings of the 16th international conference on World Wide Web[C].ACM，2007：191-200.

[11]T.C.Mills. Time series techniques for economists[J]. Cambridge University Press，1991.

基金項(xiàng)目：本文系校級(jí)（廣東科學(xué)技術(shù)職業(yè)學(xué)院）基金培育項(xiàng)目“基于深度學(xué)習(xí)算法的圖像識(shí)別技術(shù)研究”（項(xiàng)目編號(hào)：XJPY202007）的研究成果之一

（作者單位：廣東科學(xué)技術(shù)職業(yè)學(xué)院）