计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
11期
41-45,51
,共6页
社会网络%线性阈值模型%信息传播%影响最大化%概率转移矩阵%贪心算法
社會網絡%線性閾值模型%信息傳播%影響最大化%概率轉移矩陣%貪心算法
사회망락%선성역치모형%신식전파%영향최대화%개솔전이구진%탐심산법
social network%Linear Threshold(LT) model%information propagation%influence maximization%probability transfer matrix%greedy algorithm
现有近似求解影响最大化算法的时间复杂度较高，为此，提出一种扩展的线性阈值模型及其概率转移矩阵，给出该模型的传播过程及规则，设计基于概率转移矩阵的影响最大化算法，并利用贪心方法寻找到 k 个最具影响的节点。该算法通过矩阵乘积的方法得到 T 时刻节点之间的影响概率，无需在每个时刻计算所有非活跃节点的边际效益，从而在较短时间内提高运行时的效率，使得在规模较大的社会网络中被影响的节点最多且信息传播范围最广。仿真实验结果表明，在大规模社会网络中，该算法对社会网络节点的影响范围广且时间复杂度低。
現有近似求解影響最大化算法的時間複雜度較高，為此，提齣一種擴展的線性閾值模型及其概率轉移矩陣，給齣該模型的傳播過程及規則，設計基于概率轉移矩陣的影響最大化算法，併利用貪心方法尋找到 k 箇最具影響的節點。該算法通過矩陣乘積的方法得到 T 時刻節點之間的影響概率，無需在每箇時刻計算所有非活躍節點的邊際效益，從而在較短時間內提高運行時的效率，使得在規模較大的社會網絡中被影響的節點最多且信息傳播範圍最廣。倣真實驗結果錶明，在大規模社會網絡中，該算法對社會網絡節點的影響範圍廣且時間複雜度低。
현유근사구해영향최대화산법적시간복잡도교고，위차，제출일충확전적선성역치모형급기개솔전이구진，급출해모형적전파과정급규칙，설계기우개솔전이구진적영향최대화산법，병이용탐심방법심조도 k 개최구영향적절점。해산법통과구진승적적방법득도 T 시각절점지간적영향개솔，무수재매개시각계산소유비활약절점적변제효익，종이재교단시간내제고운행시적효솔，사득재규모교대적사회망락중피영향적절점최다차신식전파범위최엄。방진실험결과표명，재대규모사회망락중，해산법대사회망락절점적영향범위엄차시간복잡도저。
Aiming at the high time complexity of some algorithms which solve the influence maximization problem, this paper proposes an extended linear threshold propagation model and the probability transfer matrix. The propagation process and rules of the model are proposed. It designs the influence maximization algorithm based on probability transfer matrix and utilizes the greedy method to find the top-k nodes with more influence power. The algorithm computes the probability effect of T instant by probability transfer matrix product. It need not compute the marginal benefit of inactive nodes at each moment. It can improve the efficiency of running in shorter time, and it can maximize the number of influenced nodes and can widen the range of information propagation in large-scale social network. Experimental results demonstrate the effectiveness and efficiency of the approach. The algorithm has wide influence range for social network nodes and has low time complexity in large social network.
