Rumor有关的方向

Rumor source detection

领域内奠基之作

这篇文章可以说是rumor source detection方向的奠基之作，发表在顶级期刊IT上。文章主要基于网络拓扑结构，从用户的观测结果出发，利用极大似然的方法推断谣言源头，并提出了高效的贪心算法。后期，基于文中所提出的“rumor centrality”概念，衍生出大量有关rumor source detection的工作。

具有近似度保证的多源头追溯

Multiple Infection Sources Identification with Provable Guarantees

这篇文章发表在顶级会议cikm上，其主要思路是将网络现有的感染情况用VI表示，也就是网络中被感染的节点数。rumor source用S表示，V(S,M) 表示在source S和传播模型M下，网络中被感染的节点数。用到的方法是，将VI集合和V(S,M) 集合的对称差定义为symmetric difference，D，那么source detection问题就转化为：寻找一个S属于VI，使得在所有可能的的V(S,M)下，D的期望最小。与传统的工作相比，这是首次提出适用于一般的网络拓扑，而且有近似度保证的infection source identification算法。

文章提出的SISI算法主要是建立在两个算法的基础上。首先，第一个是取样算法，就是构建RR sets，即在网络中随机选择一个节点，在给定的迭代次数t以内，在VI集合内找到能够感染它的节点集合Ri（反向思路），这里的Ri就是节点v的RR sets，v记作Ri集合的源节点。然后，将所有源节点在VI内的RR 集的集合定义为Rblue，所有源节点不在VI内的RR 集的集合定义为Rred。那么我们希望找到的S集合，应该是尽可能多的感染VI里的节点，尽可能少的感染VI以外的节点，也就是说希望S和Rblue里的Ri交集非空，和Rred里的交集为空。换句话说，我们的目标是找到一个S属于VI，使得Rblue里和S不相交的RR集的个数+Rred里和S相交的RR集的个数的和尽可能的小。然后，对每个RRset，定义了一个随机变量Xj，当这个RRset在Rblue里且和S不相交，或者这个RRset在Rred里且和S相交时，它的值为1，否则为零。然后文章证明了，X_j的期望等于symmetric difference的期望值除以n。直观来看，就是说平均每个节点造成的symmetric difference等于它的RRset在Rblue里且和S不相交，或者这个RRset在Rred里且和S相交的概率。因此，问题可以近似为找一个S属于VI，使得Rblue里和S不相交的RR集的个数+Rred里和S相交的RR集的个数的和最小。注意到这里有一个问题，就是取多少个RR集合怎么取的问题，这个在SISI算法中考虑把symmetric difference框架下的目标函数转化为RR集合下的之后，再做进一步处理，也就是文章提出的第二个算法，叫做submodular cost covering算法，就是把这个RR集合下的优化问题转化为submodular cost问题，这样目标函数就是一个子模函数。最后，就可以通过这两个算法建立SISI算法，首先设定一个值\gamma，按照取样算法随机取样\gamma个节点的RR集，然后在这个取样下，执行子模花费算法，计算目标函数的值是否达到精度要求，如果没有就继续取样，执行子模花费算法，再判断目标函数是否达到精度要求……最后直至达到要求停止。

Rumor Blocking

加入正向消息作用的谣言传播

An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks

这篇文章是通过在网络中加入positive cascade来进行rumor blocking。整个网络中，rumor和positive cascade同时进行，节点被首先到达的那个状态感染，如果同时到达，则被rumor感染。rumor和positive cascade都是通过seed nodes扩散，考虑的扩散模型都是IC模型，并且假设两个seed nodes集合不相交。Rumor blocking的主要思想是让positive information先于rumor到达网络中没有被感染的节点。那么，rumor blocking问题就转化为在给定budget的条件下，寻找positive information的seed nodes set，使得被positive信息激活的节点数达到最大值。事实上还是IM问题。

大概的思路是将最终被positive激活的节点数定义为所有可能的传播情况下，被激活的节点数的期望值。这里，引入了realization的定义，即一个确定性的IC图，表示一种传播情况。那么最终被positive激活的节点数定义为所有可能的realization下，被positive cascade激活的节点数的期望值。然后证明了最终被感染的节点数是种子节点集合的子模函数。如果用贪心算法求解的话，因为realization的数量都是指数级的，所以扩展性很差，因此，本文提出了一种新的算法。和上一篇的思路相同，首先进行取样，得到网络中节点的Random R-tuple T，实际上就是之前的RR集合，只是名字不一样。和上一篇RR集合得到的方式不同的是，这里在搜索可能感染节点v的节点的时候，终止条件有两种情况，一种是因为再反向图中，没有节点能够进一步感染，另一种就是遇到rumor的种子节点。

接着，和cikm那篇套路一样，定义一个随机变量x，在种子节点集合为S时，如果T和S有交集或者T是由于没有节点能够进一步感染而终止的，则x=1，否则x=0。然后，同样证明了x的期望等于系统中最终被S感染的节点数的期望值除以n。直观来看，即平均每个节点感染的节点数等于节点的T和S交集非空的概率，即S中有节点能够影响这个节点的概率。然后按照前面的取样算法，随机选择l个节点，得到l个R-tuple。那么前面那个概率就可以用l个节点的x的和（定义为F）来近似，那么问题就转化为寻找一个有k个种子节点的集合，使得F最大。

基于上面的分析，问题就转化为一个集合覆盖问题，可以利用贪心算法，每一步都选择能够覆盖最多Ti集合的节点作为种子节点，总共进行k步迭代。同时，这个贪心算法能够得到1-1/e的近似度保证。最后，就是估计这个种子节点的影响范围，是直接将F除以l，就是利用平均数来估计期望，然后给出了证明，取多少个样本，得到多少近似度保证。