计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2015年
2期
238-248
,共11页
曹玖新%董丹%徐顺%郑啸%刘波%罗军舟
曹玖新%董丹%徐順%鄭嘯%劉波%囉軍舟
조구신%동단%서순%정소%류파%라군주
社交网络%影响最大化%独立级联模型%k-核%社会计算
社交網絡%影響最大化%獨立級聯模型%k-覈%社會計算
사교망락%영향최대화%독립급련모형%k-핵%사회계산
social networks%influence maximization%independent cascade model%k-core%social computing
社会网络中影响最大化问题是指在特定传播模型下,获取一个指定大小的节点集合,使得该集合在网络中的聚合影响力最大.针对贪心算法运用于大规模社会网络时存在效率低下且不可扩展的问题,文中提出基于核数层次特征和影响半径的启发式算法——核覆盖算法(Core Covering Algorithm,CCA).该算法首先引入k-核概念,基于k-核分解求出每个节点的核数,然后根据核数分布的层次性,引入节点的影响半径参数,最后综合核数和度数两个属性,找出影响力节点集合.文中在两个数据集和两种传播模型上进行了实验,结果表明:(1)在传播概率较大的独立级联模型(Independent Cascade Model,IC)下,CCA能取得比现有启发式算法更优的影响效果;(2)在三价(TRIVALENCY Model,TR)模型下,CCA的表现也同样优于其他启发式算法;(3)与其他启发式算法相比,CCA的运行时间更少.
社會網絡中影響最大化問題是指在特定傳播模型下,穫取一箇指定大小的節點集閤,使得該集閤在網絡中的聚閤影響力最大.針對貪心算法運用于大規模社會網絡時存在效率低下且不可擴展的問題,文中提齣基于覈數層次特徵和影響半徑的啟髮式算法——覈覆蓋算法(Core Covering Algorithm,CCA).該算法首先引入k-覈概唸,基于k-覈分解求齣每箇節點的覈數,然後根據覈數分佈的層次性,引入節點的影響半徑參數,最後綜閤覈數和度數兩箇屬性,找齣影響力節點集閤.文中在兩箇數據集和兩種傳播模型上進行瞭實驗,結果錶明:(1)在傳播概率較大的獨立級聯模型(Independent Cascade Model,IC)下,CCA能取得比現有啟髮式算法更優的影響效果;(2)在三價(TRIVALENCY Model,TR)模型下,CCA的錶現也同樣優于其他啟髮式算法;(3)與其他啟髮式算法相比,CCA的運行時間更少.
사회망락중영향최대화문제시지재특정전파모형하,획취일개지정대소적절점집합,사득해집합재망락중적취합영향력최대.침대탐심산법운용우대규모사회망락시존재효솔저하차불가확전적문제,문중제출기우핵수층차특정화영향반경적계발식산법——핵복개산법(Core Covering Algorithm,CCA).해산법수선인입k-핵개념,기우k-핵분해구출매개절점적핵수,연후근거핵수분포적층차성,인입절점적영향반경삼수,최후종합핵수화도수량개속성,조출영향력절점집합.문중재량개수거집화량충전파모형상진행료실험,결과표명:(1)재전파개솔교대적독립급련모형(Independent Cascade Model,IC)하,CCA능취득비현유계발식산법경우적영향효과;(2)재삼개(TRIVALENCY Model,TR)모형하,CCA적표현야동양우우기타계발식산법;(3)여기타계발식산법상비,CCA적운행시간경소.
