信息传播网络中信息源推断问题的研究

伴随着科技的进步、Internet网络的发展,以及智能终端的快速普及,4G、WIFI等高速无线接入技术的迅猛发展,现代网络(如社会网络、无线通信网络、交通网络和在线社交网络等等)在网络规模和复杂性都得到大幅的增加,使得信息的传播更加便捷。于是,带领我们来到了信息爆炸的大数据的时代。网络中纷繁的信息传播现象无处不在,同时也使我们更容易受到来自于网络的风险。网络中比如流行性疾病,计算机病毒,社交网络谣言等恶意信息的传播,严重的妨害了社会秩序,带给社会在人力和经济上的巨大损失。因此快速而准确的推断出网络中信息传播的源节点,可以帮助控制和防止这些网络风险的发生,从而使网络风险给社会带来的损失降到最低。针对信息源推断问题,本文的主要贡献如下：1)研究了基于SI模型的多样本观测下的信息源推断问题。考虑网络中同一个源节点可能发出多条信息/谣言,提出了一个基于联合谣言向心性的信息源推断框架,并对于规则树网络,给出了明确的正确检测概率的性能表现。结果表明,即使仅仅是两个样本观察,正确检测概率随着网络节点度的增加而单调递增,至少两倍于单样本检测,并且当度足够大时,正确检测概率趋于1。进一步,我们证明了对于度大于2的规则树图,正确检测概率随着样本数k的增加而单调递增,当k足够大时,检测概率也趋于1。这表明丰富的多样性和丰富的连通性都可以提高检测性能。最后我们又将我们提出的算法推广到一般树图以及实际网络中,如小世界网络和无标度网络等,来分析多样本下的信息源检测性能,都可以得到多样本检测可以显著地提高检测性能。2)研究了基于SI模型的带有时序信息的信息源推断问题。考虑了部分感染节点可以提供感染顺序的信息,我们把这些感染节点叫做“锚节点”。提出了一个基于受限谣言向心性的最大似然估计器和与之对应的信息源推断算法。受限谣言向心性是一个考虑了锚节点的感染顺序的网络拓扑量。此外,设计了一个次优的RC启发式快速算法。次优的RC算法比最优的RRC算法的正确检测概率低,但其计算复杂度低,计算更快速。结果表明,当随机选取的m个锚节点中只已知最先被感染的节点的情况下,我们发现当锚节点占总感染节点数目的比例比较小时,已知锚节点的感染顺序对于信息源的检测性能影响很大;而互相连通的m个锚节点会帮助正确检测信息源的概率得到大幅提高,即使对于线性网络。最后我们将提出的算法推广到一般树图以及实际网络中,如纽曼科学合作网络和推特转发关系网络等,得到带有时序信息的信息源推断可以有效地提高检测性能。3)研究了其他场景下的信息源推断问题,具体为3小部分。首先,我们研究了SIS模型下的信息源推断。我们研究SI与SIS模型的关系,设计算法还原出SIS模型中一些曾经被感染,但已经恢复的感染节点。并将单样本拓展到多样本下的信息源推断,提出了一个基于联合谣言中心的SIS模型下的启发式算法。最后我们将提出的算法应用在一般树图以及实际网络中,进行SIS模型下的检测性能分析。结果显示我们提出的启发式算法提供了良好的检测性能,而且多样本观测相比单样本,可以显著的提高检测性能。其次,我们研究了基于SI模型的多信息源推断问题。我们通过构造互相连通的多信息源最大似然检测器,利用数理统计的方法分析规则树图下的正确检测概率。然后设计算法在规则树图,一般图以及实际图中进行多信息源检测的性能分析,并将单样本下多信息源推断拓展到多样本。结果显示我们提出的算法提供了良好的检测性能,而且多样本观测相比单样本,可以显著的提高检测性能。最后,我们研究了基于SI模型的多样本序贯检测下的信息源推断。不同于研究点一的多样本观测下的信息源推断,这里研究的多样本序贯观测考虑的网络中只有一个信息／谣言进行传播感染。我们在不同的时刻,先后对网络进行观测,分别得到序贯观测下的多个感染节点图。我们证明了多样本序贯观察相比最早的观测样本并不能帮助提高检测性能。这同时也揭示了要尽早进行信息源推断的必要性。