[發明專利]基于信任的社會網絡最大化影響節點的計算方法

在審

• 申請號: 201410234220.0
• 申請日: 2014-05-29
• 公開（公告）號: CN104008163A
• 公開（公告）日: 2014-08-27
• 發明（設計）人: 張波;李美子;宋倩倩;胡斯卉
• 申請（專利權）人: 上海師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海申新律師事務所 31272
• 代理人: 劉懿

技術領域

本發明涉及社交網絡技術領域，更具體的說，是基于信任的社會網絡最大化影響節點的計算方法。

背景技術

近年來，隨著Internet的普及和飛速發展，大量的社會網絡脫穎而出，如基于戀愛關系的Friendster，基于工作關系的LinkedIn等。社會網絡是社會個體和個體之間由因互動而形成的關系組成的復雜網絡。這種復雜的社會網絡，對信息的傳播和擴散起著至關重要的作用，同時社會網絡是一把雙刃劍。一方面利用社會網絡方便人們的交流和傳播信息，比如，社會網絡在反映廣大群眾真實的想法發面有巨大的作用。同時，通過社會網絡使政府的一些工作處于人民的監督之下，為營造一個良好的社會環境起著積極的作用。另一方面，也給一些不法分子利用社會網絡做出對國家和人民有害的事情以機會。因此，在利用社交網絡時，如何做到揚長避短，有效監督，也是現今社會網絡發展的主要問題。鑒于一些大型的社會網絡的成員數目龐大，且相互之間的關系更加復雜，最終會對人們的行為產生影響。它們的出現給傳統網絡的社會最大化帶來了巨大的挑戰。已經有不少相關方面的研究。傳統的如Kemple和Kleinberg提出的自然爬山貪心算法，每一步都選取當前最具有影響的節點，但是對于大型社交網絡復雜度太高，并且沒有綜合考慮節點之間的信任度問題，并不實用。田家堂等人基于線性閾值提出了一種新式的混合式影響最大化算法，該算法分為兩個階段：啟發階段選取潛在影響最大的節點，貪心階段選取影響最大的節點，但是沒有考慮到不同的節點激活閾值不同的問題，同樣也沒有對節點之間的信任度進行考慮。陳浩等人提出的基于閾值的社會網絡最大化影響，對不同的節點激活閾值不同的問題進行了改進，但是同樣沒有考慮到節點之間的信任度的重要性，忽略了其對社會網絡的最大化產生的影響。

如前所述，當前社會網絡的社會最大化問題研究，一般都是基于線性閾值模型和獨立級聯模型。目前針對社會網絡影響最大化的研究，主要集中在獨立級聯模型下利用次模特性來減少貪心算法的復雜度上。但是都只是考慮了節點之間的影響，未曾對節點之間的信任度進行考慮。由于考慮的局限性，導致研究方法的不完善，使得最終選取的社會網絡最大化影響節點的集合所取得的影響范圍會相對較小。

發明內容

本發明的目的針對現有技術中存在的缺失和不足，提出基于信任的社會網絡最大化影響節點的計算方法。

本發明是在社交網絡下進行的相關問題的研究，由于社交網絡是一個抽象且復雜的對象，為了方便分析，引入了圖論的方法，將抽象化的社交網絡形象化。并引入信任這一元素，考慮信任對激活節點的重要影響，將節點之間的信任度和影響值結合，得出綜合影響值，再根據綜合影響值得出社會網絡影響最大化節點。

本發明，基于線性閾值模型提出一種基于節點之間信任的啟發式算法(如圖1所示)，其基本流程：

首先，通過分析節點之間的交易情況計算出節點之間的信任度，根據節點之間距離的遠近計算出節點間的影響值，對節點的信任度和影響值進行綜合，得出節點的綜合影響，將節點的綜合影響和該節點當前可以激活的節點數進行綜合，找出潛在影響最大的節點，將選取的節點加入到節點集中。

其次，選取影響最大的節點。

最后，將選取到的節點集用于發展社交網絡。

本發明基于信任的社會網絡最大化影響節點的計算方法，具體步驟為：

A.定義社交網絡和社交網絡最大化影響節點的發現、選取

B.啟發階段：(1)若未激活節點v為已激活節點u的出度節點，則v對u的信任是直接信任,計算直接信任；若v是u的可達節點，則v對u的信任是間接信任，計算間接信任。(2)若未激活節點v為已激活節點u的出度節點，則u對v的影響是直接影響，計算直接影響；若v是u的可達節點，則u對v的影響是間接影響，計算間接影響。(3)結合上述兩種情況計算出的影響值和信任值，計算節點u的綜合影響。(4)根據以上步驟得出的節點綜合影響值和可激活節點數目，計算出節點的社會網絡影響。(5)將啟發階段選取的社會網絡影響最大的節點加入到社會網絡影響最大化節點集合中。

C.貪心階段：從剩下的節點中，選取當前擁有最多可激活節點的節點，加入到社會網絡影響最大化節點集合中。

D.社會網絡影響最大化節點集合的生成。

其中，所述步驟A的具體過程為：

所述社交網絡以形式化為一個圖G的一個有序的二元組<V,E>,