近似线性时间的社团结构动态演化挖掘算法

探测网络社团结构对于分析、设计复杂的自然或工程网络至关重要,然而现有的探测技术主要依托于最优化和启发式算法,不能兼顾计算效率和准确性。因此提出了一种基于演化迭代技术的动态社团探测算法,它能准确高效地发现网络中的社团结构。首先引入了一个离散时间的动态系统,通过描述社团划分收敛到特定指标最优的演化轨迹来确定社团划分。接着提出了一个一般化的指标函数,以确定网络中最优的社团数量及最稳定的社团结构。该指标函数极具概括性,改变相应的参数即可引申到各种已广泛应用的指标函数。针对参数选择的困难,利用图生成模型自动确定社团划分的指标函数。此算法效率很高,计算复杂度与稀疏网络中的节点数量呈近似线性关系。最后,在人工和真实网络中进行了大量的仿真实验来测试算法表现,结果显示所提算法能够揭示很多有价值的信息。     

基于拓扑路径的网络演化传播机制研究

现有的社会网络信息传播模型主要分析传播的途径,将传播过程与节点的度相结合,而传播媒介常常被忽略。在现实世界的网络中,传播源作为一个物理传播媒介通常由特定的路径从一个节点传播到另一个节点(基于路径的传播)。本研究不再局限于节点的总体行为分析,而是分别考虑每个节点的状态转换,用连续状态的马尔科夫链分析来模拟传播源和路径对传播行为的影响。该方法通过引入平均场近似,将基于路径的传播机制的计算复杂度从指数级别降低到多项式级别;定义了同时包含路由选择和交通信息的传播特性矩阵,并得出了基于路径传播的关键传播阈值。当有效传播率低于关键传播阈值时,传播就会逐渐消亡,因此可以运用该关键传播阈值来促进或抑制基于路径的传播。最后,除了随机无标度网络,引入了现实世界网络交通作为研究案例来对比基于连接和基于路径的传播行为,结论表明所提模型在社交网络中的传播具有高度持续性和极强的稳定性。