论文部分内容阅读
在互联网快速发展的时代背景下,现实世界中网络逐渐变得越来越复杂,挖掘复杂网络背后蕴含的数据价值显得愈发重要。社区划分技术引发学术界和工业界越来越多的关注,它能够发现网络中固有的社区结构,并在社会、商业、生物、医药、疾病防控和反恐等领域都具有广泛的应用。本文主要针对社会网络中的社区发现算法进行研究,其主要工作和贡献如下:(1)由于标签传播算法在社区发现中存在不稳定性,针对这一问题,本文提出一种基于自适应H-index的标签传播算法(AHLPA)。该算法基于改进的H-index来衡量网络中节点的影响力,并依据节点影响力和扩展的多层邻居节点给出节点重要性的定义,对节点进行更加细粒度的刻画。算法利用节点重要性对节点更新序列进行排序,并重新优化节点选择标签的策略,进一步减少随机性。实验结果表明AHLPA算法在性能和稳定性上都具有较大提升。(2)对于重叠社区,基于边划分的算法具有天然的优势,但也存在不少问题,本文提出一种基于边的标签优化算法(LinkLPAm)。首先,基于边的网络规模一般较原始网络扩大若干倍,因此采用基于边的粗糙团初始化边标签,这样不仅能够保证初始解的质量,还能够加速算法收敛。其次,结合标签传播和优化算法的思想进行基于边的社区发现。最后,根据社区相似性度量对社区进行基于贪心策略的合并,这样可以避免产生相似或过小的社区。实验仿真结果表明该算法的有效性和可用性。(3)针对一般的局部社区算法采用贪婪地将节点加入到局部社区的策略会陷入局部最优的问题,本文提出一种基于简单概率模型的局部社区发现算法(LCDGAP)。该算法主要松弛了节点加入局部社区的条件,使用局部模块度M作为节点与社区的紧密程度的度量,当节点的局部模块度增益Δm<0时,允许节点以一定的概率p加入到社区中。同时,提出一种简单概率模型代替模拟退火算法中的概率公式平衡算法的性能和时间效率。最终实验结果证明,该方法不仅有效地减少参数,而且在不降低Precision值的情况下,大大提高算法的Recall值。(4)设计并实现用户数据检索与可视化系统,并将本文提出的核心算法应用在工程实践上。