论文部分内容阅读
随着互联网的普及，越来越多的人加入社交网络展示自己的生活。社交网络的即时性使得信息和谣言可以在网络上很快传播，在线社交网络的病毒式营销成为广告的新趋势。由此启发，许多工作研究了怎样最大化信息的传播，也就是所谓的影响力最大化问题。深入理解信息在社交网络中的传播机制，以及如何控制疾病的传播、舆论的导向和营销策略的选择已经成为研究热点，影响力最大化问题和传播模型已成为许多领域涉及的重要内容。 影响力最大化旨在从网络中选择k个种子节点，使得这k个种子节点通过传播模型产生的影响传播范围最大。这个问题已经被广泛研究，但是大多的工作专注于次模的影响力传播模型。受现实的传播现象启发，本论文探讨了非次模设定下的影响力最大化问题。在通用阈值模型框架下，本论文定义了一类被次模上下界紧紧夹住的非次模阈值函数（ε-次模逼近函数），讨论图中有部分节点是ε-次模逼近阈值函数的情况。我们首先通过NP完全归约证明了不可近似性结论:即使n个节点的图中只有nγ个ε-次模逼近节点，也不存在近似比为1/nγc的算法，除非P=NP，其中γ∈(0.1)且c是依赖于ε的常数。然后我们针对有l个ε-次模逼近节点的图设计了近似比为(1-ε)l(1-1/e)的算法。最后我们在一系列真实的社交网络数据上做了对比试验，实验结果表明我们提出的近似算法要比其他基准算法效果更好。 此外本论文研究了另一种阈值函数—k-激活函数，这种阈值函数对应着一个节点只有在其k≥2个邻居都被激活后自己才会被激活的传播模型。在Kleinberg的小世界网络模型中，强连接被认为是底层网格上确定的边，而弱连接指连接相距较远的节点之间的随机边。节点u和节点v通过一条弱连接相连的概率正比于1/|uv|α，此处|uv|是节点u和v之间的网格距离，而α≥0是小世界网络模型的参数。本论文类比Kleinberg的分散式路由，提出了基于k-激活阈值函数的路由（简称k-激活路由），同时对Kleinberg小世界网络上k-激活路由时间进行了理论分析，求得k-激活路由的路由时间在所有α范围内的n的多项式的下界（n是网络中节点的个数）。