基于線性閾值模型的社交網(wǎng)絡(luò)影響最大化研究.pdf

1、近年來，隨著網(wǎng)絡(luò)技術(shù)的不斷完善，社交網(wǎng)絡(luò)得到了迅猛的發(fā)展，如CSDN、BLOG、Weibo等。隨著信息的高速傳播，影響最大化問題成為社交網(wǎng)絡(luò)中的熱門研究話題。影響最大化的研究對(duì)市場營銷、廣告宣傳以及輿情控制等方面具有重要意義。Kempe證明了影響最大化是NP-hard問題，并提出了貪心算法。貪心算法能夠達(dá)到(1-1/e)的近似最優(yōu)，但其計(jì)算開銷巨大，不能適用于大型網(wǎng)絡(luò)。啟發(fā)式方法，能夠快速地找出種子集合，但是不能保證影響的傳播范圍?；旌?/p>

2、式算法采用啟發(fā)式和貪心相結(jié)合的方式，有效的解決了貪心算法的時(shí)間開銷問題。在啟發(fā)階段，混合式算法利用節(jié)點(diǎn)鄰域信息選取最具“潛力”節(jié)點(diǎn)，這些節(jié)點(diǎn)能積累大量的影響力使得周圍未激活的節(jié)點(diǎn)更容易被激活;在貪心階段，大量的節(jié)點(diǎn)已被激活或者更容易被激活，從而貪心的時(shí)間開銷得到了大幅度的降低。但是，如何選取最有潛力節(jié)點(diǎn)以及怎樣加快貪心尋找，仍然是一個(gè)待解決的問題。
　　本研究針對(duì)以上問題，提出了基于H階鄰居的混合式算法，旨在擴(kuò)大最終的傳播范圍的同

3、時(shí)，減少算法的時(shí)間復(fù)雜度?；贖階鄰居的混合式算法同樣采用兩個(gè)階段實(shí)現(xiàn)種子節(jié)點(diǎn)的選取:啟發(fā)階段和貪心階段。在啟發(fā)階段，由于大型社交網(wǎng)絡(luò)的復(fù)雜性，我們將目光由直接出邊鄰居轉(zhuǎn)到了H階鄰居。并且在考慮節(jié)點(diǎn)對(duì)周圍鄰居的影響力的同時(shí)，也考慮了周圍鄰居自身待激活閾值的大小?；诖吮疚奶岢隽艘粋€(gè)基于H階鄰居計(jì)算潛力值的方法，該方法較準(zhǔn)確地衡量了每個(gè)節(jié)點(diǎn)的“潛力”。在貪心階段，基于H階鄰居的混合式算法通過構(gòu)建局部有向無環(huán)圖的方式，實(shí)現(xiàn)了貪心的快速尋找。