[發(fā)明專利]基于文化基因算法的社交網絡影響最大化方法

有效

• 申請?zhí)枺?/td>: 201410674364.8
• 申請日: 2014-11-21
• 公開（公告）號: CN104361462B
• 公開（公告）日: 2017-09-05
• 發(fā)明（設計）人: 公茂果;馬晶晶;沈波;馬文萍;羅恩湖;馬里佳;曾久琳;蔡清;王爽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 陜西電子工業(yè)專利中心61205
• 代理人: 王品華,朱紅星

技術領域

本發(fā)明屬于社交網絡技術領域，特別涉及一種找出社交網絡中具有最佳影響力個體組合的方法，可用于分析和研究社交網絡的信息傳播機制。

背景技術

社交網絡是現代生活中最為常見的也是最為直觀的復雜社會網絡，它由網絡中每個個體的人際關系網絡構成。其中，網絡中的每個節(jié)點代表社會生活中的每一個個體，而網絡的邊就是個體相對應的人際關系，常見的社交網絡有合作網絡、信任網絡以及交友網絡等。由于個體之間的相互交流和人際關系與我們的生活、學習以及工作密切聯系，因此對社交網絡進行分析對人類社會有著重要的研究意義和價值。

近年來，隨著Web 2.0的出現和互聯網信息技術的迅猛發(fā)展，一系列的在線交友網絡出現在人們的生活當中，具有代表性的有Facebook、Twitter、QQ以及目前快速發(fā)展的微博社交網絡平臺等。這些在線社交網絡不受空間和時間的限制，能夠使人們交流越來越頻繁，聯系也越來越緊密，極大地推動了社交網絡的發(fā)展。社交網絡的共同特點就是規(guī)模龐大，使用人群的年齡、行業(yè)等復雜多樣，且設計的話題覆蓋面廣，信息量大。

社交網絡的信息傳播，作為社會網絡的熱點研究話題，是理解、獲取和預測市場營銷、社會安全以及Web搜索等領域中信息傳播過程的基礎和依據。目前，眾多企業(yè)已經廣泛地利用社交網絡的信息傳播機制，將社交網絡視為市場營銷的平臺，進行新產品和新服務的推廣。相比于傳統(tǒng)的方法，這種市場營銷手段往往能夠以很小的代價，達到以一傳百甚至傳千的效果，從而使企業(yè)獲得極大的利潤。社交網絡影響最大化問題就可以具體解釋為，在社交網絡中推廣某種新型產品或者服務時，如何選擇首次推廣的用戶從而使得該產品或服務由其推廣到網絡中更多的個體，或者將“種子短信”發(fā)給哪些手機用戶可以獲得更大范圍的轉發(fā)；從另一個角度來講，當傳染病來臨時，應該采取何種接種免疫策略來避免和控制傳染病的傳播，或者根據網絡的信息傳播機制，如何有效地控制在線社交網絡中的謠言傳播，維護網絡安全等。

目前，社交網絡信息影響最大化的研究已經涉及到社會學、經濟學、信息傳播學、統(tǒng)計學以及計算機網絡學等多個領域，其中較為典型的社交網絡包括科學家合作網絡、電子郵件網絡、金融信任網絡以及復雜多樣的在線交友網絡等。關于如何去定量地分析和理解以及如何有效地解決社交網絡信息影響最大化問題，目前也已經引起科學界的廣泛關注和研究。除此之外，其背后蘊藏的深刻的社會意義和巨大的商業(yè)價值也在很大的程度上促進了該問題的研究和發(fā)展。

在現有的針對社交網絡信息影響最大化問題的研究中，其內容主要分為兩個方面，分別是如何建立合理的動力學模型去分析和模擬真實的社交網絡信息傳播機制以及在此基礎上，如何挖掘網絡中可以使得信息傳播最大化的種子節(jié)點集合。目前，在網絡信息傳播領域中，較為常用的兩種基本動力學分析模型分別稱為獨立級聯模型和線性閾值模型，其根據網絡的不同特征，分別從不同地角度分析了信息如何在網絡中進行傳播。除了上述的兩種傳播機制，還有最初針對傳染病傳播機制的SIR模型和SIS模型。

網絡信息影響最大化問題最早為經濟市場學領域的產品推廣問題。商家為了廣泛推廣其產品，如何有選擇地去推廣給一些有影響的人群，從而使產品達到最大范圍的推廣。Domingos和Richardson在“Mining the network value of customers”(《Processdings of the ASM SIGKDD Conference on Knowledge Discovery and Data Mining》，2001，page 57-66)中第一次將這個問題以一個算法問題提出來，并且通過使用一種基于概率模型的方法去嘗試解決它。在“Maximizing the spread of influence through a social network”(《Processdings of the ASM SIGKDD Conference on Knowledge Discovery and Data Mining》，2003，pages 137-146)一文中Kempe等人將該問題闡述為一個組合優(yōu)化問題，稱之為網絡影響最大化問題，并通過提出一種基于爬山策略的貪婪算法對其進行了求解。