计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
1期
59-63
,共5页
王俊%余伟%胡亚慧%李石君
王俊%餘偉%鬍亞慧%李石君
왕준%여위%호아혜%리석군
社交网络%影响力最大化%启发式算法%3-layer局部中心度%贪心算法
社交網絡%影響力最大化%啟髮式算法%3-layer跼部中心度%貪心算法
사교망락%영향력최대화%계발식산법%3-layer국부중심도%탐심산법
Social network%Influence maximization%Heuristic algorithm%3-layer local centrality%Greedy algorithm
社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广.一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络.基于度中心性的启发式算法简单但准确度不高；基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点,但计算复杂度也过高.考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值.基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点进行激活；运用贪心算法选取剩下的一部分种子节点:每一次都选取具有最大影响增量的节点作为种子节点进行激活.实验表明,该混合算法具有很好的激活范围以及非常低的时间复杂度.
社交網絡影響最大化問題是指如何尋找網絡中有限的初始節點,使得影響的傳播範圍最廣.一些貪心算法可以得到較好的影響範圍,但是因時間複雜度太高而不適用于大型社交網絡.基于度中心性的啟髮式算法簡單但準確度不高；基于介數中心性、接近中心性等全跼指標的啟髮式算法可以較好地識彆影響力最大的節點,但計算複雜度也過高.攷慮網絡節點深層次結構對影響擴散的作用併權衡計算複雜度與準確度,定義瞭3-layer跼部中心度,以計算節點的潛在影響力值.基于線性閾值模型,啟髮選擇一部分種子節點:每一次都選取潛在影響力最大的節點作為種子節點進行激活；運用貪心算法選取剩下的一部分種子節點:每一次都選取具有最大影響增量的節點作為種子節點進行激活.實驗錶明,該混閤算法具有很好的激活範圍以及非常低的時間複雜度.
사교망락영향최대화문제시지여하심조망락중유한적초시절점,사득영향적전파범위최엄.일사탐심산법가이득도교호적영향범위,단시인시간복잡도태고이불괄용우대형사교망락.기우도중심성적계발식산법간단단준학도불고；기우개수중심성、접근중심성등전국지표적계발식산법가이교호지식별영향력최대적절점,단계산복잡도야과고.고필망락절점심층차결구대영향확산적작용병권형계산복잡도여준학도,정의료3-layer국부중심도,이계산절점적잠재영향력치.기우선성역치모형,계발선택일부분충자절점:매일차도선취잠재영향력최대적절점작위충자절점진행격활；운용탐심산법선취잉하적일부분충자절점:매일차도선취구유최대영향증량적절점작위충자절점진행격활.실험표명,해혼합산법구유흔호적격활범위이급비상저적시간복잡도.
