-
在线社交网络逐渐成为人们不可或缺的重要工具, 识别网络中具有高影响力的节点作为初始传播源, 在社会感知与谣言控制等方面具有重要意义. 本文基于独立级联模型, 给出了一个描述有限步传播范围期望的指标—传播度, 并设计了一种高效的递推算法. 该指标在局部拓扑结构信息的基础上融合了传播概率对影响力进行刻画, 能够较好地反映单个节点的传播影响力. 对于多传播源影响力极大化问题, 本文提出了一种基于传播度的启发式算法—传播度折扣算法, 使得多个传播源的联合影响力最大. 最后, 将上述方法应用到三个真实网络中, 与经典指标和方法相比, 该方法不需要知道网络的全局结构信息, 而是充分了利用网络的局部结构信息, 可以较快地筛选出高传播影响力的传播源.On-line social networks have gradually become an indispensable tool for people. Identifying nodes with high influence in the network as an initial source of communication is of great significance in social perception and rumor control. According to the independent cascade model, in this paper we present an index describing the finite step propagation range expectation as the degree of propagation, and design an efficient recursive algorithm. Based on the local topology information, the index combines the propagation probability to characterize the influence, which can better reflect the propagation influence of a single node. For a single propagation source influence ordering problem, the node degree of propagation and propagation capability are better consistent with each other. And the propagation degree can well describe the propagation influence of nodes under different networks and propagation probabilities. For maximizing the multi-propagation source influence, in this paper we propose a propagation-based heuristic algorithm which is called propagation discount algorithm. This algorithm makes the joint influence of multiple propagation sources maximized. Finally, in this paper we apply the above method to three real networks, showing better effects than the classic indicators and methods. The algorithm has three advantages. First, the expected value of the final propagation range of each node in the small network can be accurately calculated. Second, the degree of propagation fully considers the local topology of the node and belongs to a locality indicator. Third, the indicator combines the effect of propagation probability and yields good outcomes under different networks and propagation probabilities.
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] -
辅助算法二 联合概率算法 输入 时间t, 节点u以及对于u的序号集W 输出 联合概率${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right)$ 1. ifW只含一个元素then 2. 找到该节点的双亲节点${{{v}}_{\left( {{i}} \right)}}$ 3. ${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right) = {{{f}}_{{{t}} - {{1}}}}\left( {{{{v}}_{\left( {{i}} \right)}}} \right) \times {{\beta }} \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$ 4. else 5. 找到传播树种${{{P}}_{{t}}}$代序号集为W的u节点, 记其双亲节点为${{{v}}_{{1}}}, {{{v}}_{{2}}}, \cdots , {{{v}}_{{l}}}$, 出现次数为$ m_1, $$ m_2, \cdots , m_l$, 这些路径对于双亲节点的序号集分别为${{{X}}_{{1}}}, {{{X}}_{{2}}}, \cdots , {{{X}}_{{l}}}$, 对于节点u的序号集分别为${{{Y}}_{{1}}}, {{{Y}}_{{2}}}, \cdots {{{Y}}_{{l}}}$. 6. for${{j}} = 0 \to {{l}}$do 7. ${{{f}}_{{t}}}\left( {{{{u}}_{{{{Y}}_{{j}}}}}} \right) = {{F}}\left( {{{t}} - {{1}}, {{{v}}_{{j}}}, {{{X}}_{{j}}}} \right) \times {{\beta }}$ 8. end for 9. ${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right) = \left[ {{{1}} - \mathop \prod \nolimits_{{{j}} = {{1}}}^{{l}} \left( {{{1}} - {{{f}}_{{t}}}\left( {{{{u}}_{{{{Y}}_{{j}}}}}} \right)} \right)} \right] \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$ 10. end if 11. return${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right)$ 
下载:
导出CSV
递推算法 求种子节点s阶传播度 输入 seed,${{\beta }}$,s 输出 ${{{d}}_{{s}}}$ 1. ${\rm Tree }_{s} = {\rm FTree }(\rm seed)$ %获取节点${{seed}}$的s阶传播树 2. 赋初值${ { {p} }_{ {0} } }\left( { { {\rm seed} } } \right) = { { {f} }_{ {0} } }\left( { { {\rm seed} } } \right) = { {1} }$, 其他情况${{{p}}_{{t}}}\left( {{u}} \right) = {{{f}}_{{t}}}\left( {{u}} \right) = {{0}}$ 3. for${{t}} = {{1}} \to {{s}}$do 4. for${{{u}}_{{y}}} \in {{{P}}_{{t}}}$do%遍历传播树中${{{P}}_{{t}}}$代的个体 5. 获得${{{u}}_{{y}}}$的双亲节点${{{v}}_{{x}}}$ %表示节点u所在传播树层中第x个u节点 6. ${{{f}}_{{t}}}\left( {{{{u}}_{{y}}}} \right) = {{{f}}_{{{t}} - {{1}}}}\left( {{{{v}}_{{x}}}} \right) \times {{\beta }} \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$ 7. end for 8. for${{u}} \in {{{P}}_{{t}}}$do 9. 获得u的序号集W %指${{{P}}_{{t}}}$代节点u出现次序构成的集合 10. 计算联合概率${{{f}}_{{t}}}\left( {{u}} \right) = {{F}}\left( {{{t}}, {{u}}, {{W}}} \right)$ 11. end for 12. for$u \in {\rm Tree}_{s}$do 13. ${{{p}}_{{t}}}\left( {{u}} \right) = {{{p}}_{{{t}} - 1}}\left( {{u}} \right) + {{{f}}_{{t}}}\left( {{u}} \right)$ 14. end for 15. end for 16. ${ { {d} }_{ {s} } }\left( { { \rm{seed} } } \right) = \mathop \sum \nolimits_{ {u} } { { {p} }_{ {s} } }\left( { {u} } \right)$ 17. return${{{d}}_{{s}}}$ 下载:
导出CSV
-
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
下载:
计量
- 文章访问数:6748
- PDF下载量:95
- 被引次数:0