首页> 外文OA文献 >Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
【2h】

Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning

机译:几何多尺度社区检测:马尔可夫稳定性和向量   分区

代理获取
本网站仅为用户提供外文OA文献查询和代理获取服务,本网站没有原文。下单后我们将采用程序或人工为您竭诚获取高质量的原文,但由于OA文献来源多样且变更频繁,仍可能出现获取不到、文献不完整或与标题不符等情况,如果获取不到我们将提供退款服务。请知悉。

摘要

Multiscale community detection can be viewed from a dynamical perspectivewithin the Markov Stability framework, which uses the diffusion of a Markovprocess on the graph to uncover intrinsic network substructures across allscales. Here we reformulate multiscale community detection as a max-sum lengthvector partitioning problem with respect to the set of time-dependent nodevectors expressed in terms of eigenvectors of the transition matrix. Thisformulation provides a geometric interpretation of Markov Stability in terms ofa time-dependent spectral embedding, where the Markov time acts as aninhomogeneous geometric resolution factor that zooms the components of the nodevectors at different rates. Our geometric formulation encompasses bothmodularity and the multi-resolution Potts model, which are shown to correspondto vector partitioning in a pseudo-Euclidean space, and is also linked tospectral partitioning methods, where the number of eigenvectors usedcorresponds to the dimensionality of the underlying embedding vector space.Inspired by the Louvain optimisation for community detection, we then proposean algorithm based on a graph-theoretical heuristic for the vector partitioningproblem. We apply the algorithm to the spectral optimisation of modularity andMarkov Stability community detection. The spectral embedding based on thetransition matrix eigenvectors leads to improved partitions with higherinformation content and higher modularity than the eigen-decomposition of themodularity matrix. We illustrate the results with random network benchmarks.
机译:可以在Markov稳定性框架内从动力学角度查看多尺度社区检测,该框架使用Markov过程在图形上的扩散来发现所有尺度的内在网络子结构。在这里,我们将多尺度社区检测重新构造为关于过渡矩阵特征向量表示的时间相关节点向量集的最大和长度向量划分问题。该公式根据时间相关的频谱嵌入提供了马尔可夫稳定性的几何解释,其中马尔可夫时间充当不均匀的几何分辨率因子,以不同的速率缩放节点矢量的分量。我们的几何公式​​既包含模块化,又包含多分辨率Potts模型,它们被证明对应于伪欧几里德空间中的向量划分,并且还与光谱划分方法相关,其中所使用的特征向量的数量与基础嵌入向量空间的维数相对应受到Louvain优化进行社区检测的启发,我们提出了一种基于图论启发式的向量划分问题算法。我们将该算法应用于模块化和马尔可夫稳定性社区检测的光谱优化。与模块化矩阵的特征分解相比,基于过渡矩阵特征向量的频谱嵌入导致改进的分区具有更高的信息含量和更高的模块化。我们用随机网络基准说明结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
代理获取

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号