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

摘要：在大數(shù)據(jù)時(shí)代的今天，如何從海量的社交媒體中尋找信息擴(kuò)散的源頭，并且預(yù)測(cè)信息擴(kuò)散的未來(lái)走勢(shì)，已成為人們非常關(guān)心的熱點(diǎn)問題，這就為數(shù)據(jù)挖掘在熱點(diǎ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)模型與線性閾值模型均需要將激活過程放置在一個(gè)個(gè)離散的輪回中，是非連續(xù)的。自主研究了一個(gè)基于連續(xù)時(shí)間馬科夫過程的模型來(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)鍵詞：馬科夫過程；信息擴(kuò)散模型；獨(dú)立級(jí)聯(lián)模型；線性閾值模型

一、前言

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

二、靜態(tài)挖掘

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

和度類似的兩種定義用戶影響力的方法是接近性核心性和中介性核心性。首先，以下公式（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)過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ò)是處于不停變化中的，因而通過靜態(tài)方法挖掘到的信息只是針對(duì)某個(gè)時(shí)間點(diǎn)的，是片面的。

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

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

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

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

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

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

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

（二）馬科夫過程

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

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

（三）基于馬科夫過程的用戶影響力定義

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

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

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

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

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

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

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

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

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

在獲得了Q矩陣后，便可以通過Q獲取傳遞概率矩陣P（t）。根據(jù)柯爾莫哥洛夫向后方程：

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

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

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

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

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

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

為了檢驗(yàn)新提出的模型擁有預(yù)測(cè)用戶影響力的能力，我們將該模型（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è)用戶和隨機(jī)的五個(gè)用戶進(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é)果即是用戶在后10天的數(shù)據(jù)當(dāng)中所傳遞到其他用戶數(shù)量。

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

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

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

參考文獻(xiàn)

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

[2]王晰巍，賈若男，韋雅楠，等.多維度社交網(wǎng)絡(luò)輿情用戶群體聚類分析方法研究[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)排序算法若干問題研究[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ò)用戶影響力排序方法研究[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é)院）