-
题名影响最大化问题中基于K-truss的投票改进算法
- 1
-
-
作者
孙飞翔
陈卫东
林天森
-
机构
华南师范大学计算机学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2022年第11期291-298,共8页
-
基金
国家自然科学基金(61370003)。
-
文摘
在社交网络的影响最大化(IM)问题中,近似算法通过大量的Monte-Carlo模拟计算节点集的影响范围,导致时间复杂度提高,而多数启发式算法在具有不同拓扑结构的图上存在稳定性较差的问题。提出基于K-truss的改进投票算法TrussVote。在投票阶段,通过引入K-truss的相关理论及算法定义节点的有效投票能力,用于表示节点对其不同邻居的投票倾向,同时在计算得票分数时考虑边的传播概率,提高解决IM问题的效率。在每轮投票结束后,将得票分数最高的节点选为种子节点。在更新阶段,结合节点间的相似性指标定义衰减因子,以有效区分邻居节点投票能力的弱化程度。此外,基于IC模型下的原始传播结果,提出传播差异作为传播范围的等价分析指标。在不同规模真实网络数据集上的实验结果表明,相比RNR、VoteRank++等算法,该算法不仅能有效降低时间复杂度,而且可在最短的时间内感染更多的节点,具有广泛的影响范围。
-
关键词
社交网络
影响最大化
投票算法
k-truss分解
IC模型
SIR模型
-
Keywords
social network
Influence Maximization(IM)
voting algorithm
k-truss decomposition
IC model
SIR model
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名基于GAS模型的k-truss分解算法
被引量：1
- 2
-
-
作者
王邠
周刚
张凤娟
-
机构
数学工程与先进计算国家重点实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2018年第6期1691-1695,共5页
-
基金
数学工程与先进计算国家重点实验室开放基金资助项目(2015A11)
-
文摘
在大规模网络中发现稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测等。针对大规模网络数据中快速、有效地发现稠密子图,提出了一种基于GAS(gather-apply-scatter)编程模型的分布式k-truss算法——GASTruss。算法采用GAS的模式完成数据同步和算法迭代,有效地克服了传统并行算法重复性计算及不能有效处理依赖关系大的数据等问题。实验选择在Graph Lab平台上进行,结果表明:与串行k-truss算法以及基于MapReduce的GPTruss算法性能相比,GASTruss算法对数据规模具有良好的拓展性,在保持算法效果的同时能有效降低时间复杂度。
-
关键词
k-truss分解
稠密子图
分布式算法
GAS模型
-
Keywords
k-truss decomposition
cohesive subgraph
distributed algorithm
GAS programming model
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
