[發明專利]一種基于節點特性的影響力最大化初始節點選取方法

有效

• 申請號: 201510072839.0
• 申請日: 2015-02-11
• 公開（公告）號: CN104616200B
• 公開（公告）日: 2017-10-10
• 發明（設計）人: 鄧曉衡;潘琰;曹德娟;朱從旭;林立新;沈海瀾;李登
• 申請（專利權）人: 中南大學
• 主分類號: G06F19/00
• 分類號: G06F19/00;G06Q50/00
• 代理公司: 中南大學專利中心43200
• 代理人: 胡燕瑜

技術領域

本發明屬于計算機技術領域，涉及一種基于節點特性的影響力最大化初始節點選取方法。

背景技術

互聯網的發展不僅為我們帶來了便捷生活方式，還使我們交流與溝通的方式發生了巨大的變化。我們交友與分享智慧的途徑也隨著在線社會網絡的發展變得更加豐富多樣。隨著越來越多的人使用諸如移動終端等更加便捷的數據交換服務，我們的社會結構和社會關系網絡變得更加復雜和緊密。一般情況下，我們使用圖結構對社會群體中的人與人之間的關系進行建模，節點代表個體，而邊或者弧代表個體之間的關系。通過在線社會網絡中用戶之間的關系，信息可以以極快的速度和極小的代價進行傳播，正因為如此，影響力在社會網絡中的傳播和分布為病毒式營銷帶來了前所未有的機遇和挑戰，如何找到初始用戶群體使得信息最終的影響傳播范圍最大已成為熱點研究領域之一。

對于影響力最大化問題，當前大部分的研究工作都是基于對傳統經典影響力級聯模型的優化，或者對啟發式算法的準確度進行改進，對于影響力的評估則主要基于網絡結構和節點度值，用戶自身的特性和用戶與用戶之間的行為相似性很少被挖掘并被應用于對節點影響力的評估中。

針對上述不足，我們提出一種對于節點初始影響力的評估方案，這種方法結合了用戶特性，用戶與行為之間關聯關系以及用戶之間行為相似度對節點之間的影響力進行評價。同時，我們依據提出的節點之間的影響力評價標準對信用進行分配，并結合貪心算法得到初始影響力最大化節點集合。

發明內容

本發明提出了一種更加真實有效的基于節點特性的影響力最大化初始節點選取方法，在評價節點之間影響力的過程中結合用戶活躍度，用戶敏感度以及用戶親密度對節點之間的影響力進行評價，根據時間特性計算節點之間的用戶影響力大小，并且結合網絡結構和用戶行為日志對信用分布和影響力的傳播過程進行構建，最后結合貪心算法選取邊際收益最大的節點得到初始影響力最大化節點集合。具體步驟如下：

步驟1：對在線社會網絡數據集進行處理，得到真實的用戶行為日志和網絡結構文件；

步驟2：遍歷用戶行為日志，對網絡中的每一個節點，分別計算用戶活躍度，用戶敏感度和用戶親密度，對u節點，用戶活躍度act(u)定義為：

代表節點u執行的行為的個數，代表節點u受到鄰居節點影響而被動執行的行為個數，代表訓練集中記錄的行為總個數，參數λ對兩種行為數量指標進行控制，取值范圍為(0,1)，用戶敏感度定義如下：

記錄節點u的所有鄰居節點中首次執行行為a的時刻，t_u(a)代表節點u最終被影響而執行相同行為a的時刻，τ_u代表節點u與其鄰居節點之間的平均延遲時間；當兩個時刻的時間跨度越長，的值就越小，用戶親密度p_v，u計算公式如下：

表示節點u和節點v執行行為種類集合的并集，表示節點u和節點v執行行為種類集合的交集；

步驟3：分別對用戶敏感度和用戶親密度進行歸一化處理，節點u的用戶平均敏感度和用戶平均親密度計算規則如下：

代表訓練集中記錄的行為，N(u)表示節點u的鄰接節點集合，v∈N(u)，初始用戶影響力定義為：

給定節點u與其鄰居節點v之間的平均延遲時間τ_v，u和節點u的初始用戶影響力iniful(u)，使用連續衰減函數對鄰接節點v和節點u之間的影響力進行變換，計算公式如下：

代表節點v對節點u對于行為a的用戶影響力，是節點v執行行為a的時刻，N_out(u)表示節點v的出鄰居節點集合，u∈N_out(v)，t_u(a)代表節點u最終被影響而執行相同行為a的時刻；

步驟4：定義分配給節點v讓其影響節點u的信用，對于任意的兩個節點v和節點u，給予節點v讓其影響節點u的總信用定義為：