Jun, 2019

Motivo: 快速模体计数通过简明编码和自适应取样

PDF
TL;DRMotivo 是一种新的随机图形态计数算法。该方法采用了两种新的改进策略，分别是设计新的高效数据结构，并采用自适应的 graphlet 采样策略，可在普通桌面设备上实现对具有数十亿个边的大型图像进行高效、准确计数，可超过当前领先的算法，编码后占用空间更小。
color codingmotif countinggraphlet samplingdata structureslarge graphs
发现论文，激发创造
  • 使用图采样计算模体数量

    本文从统计学角度研究了网络采样和子图统计中的几个问题，提出了一些估算方法，并给出了理论与实验结果。

    Feb, 2018

  • 社交网络分析中的模式聚类和重叠聚类

    本文引入了一种新的聚类范式 —— 模式聚类，该文章探讨了模式聚类在社交网络社区分析中的应用，以及通过模式覆盖算法实现的重叠聚类与潜在特征推断等问题。

    Dec, 2016

  • 高效估计大型网络的基序统计量

    本文提出了一种基于抽样的算法，有效地从大规模网络中准确估算子图统计量，并展示实验结果表明其能更加快速地完成与现行技术相同准确度的查询量（样本量）

    Jun, 2013

  • 为可交换图生成模型计算预期基序计数

    本文提出了一种可扩展的估算预期模体计数的过程，适用于神经和贝叶斯图数据方法中使用的类型的生成混合模型。

    May, 2023

  • 通过（超）图划分进行本地模体聚类

    本文针对基于分布的局部聚类问题，提出了结合超图和图模型的新方法，通过组合优化算法求解，并在三角形图案实验中表现出了较高的性能表现。

    May, 2022

  • 大规模图中奇异子结构的快速准确挖掘：摇摆随机游走

    本文提出了一种新的算法 Waddling Random Walk（WRW），用于估计任意大小的图相对浓度，并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集，该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。

    May, 2016

  • 大规模复杂网络着色

    提出一种基于 egonet 属性和并行算法的大规模复杂网络图染色方法，几乎在所有网络中都显示出优异的性能，并获得近乎最优解。

    Mar, 2014

  • Motiflets -- 时间序列中基序的快速准确检测

    本文提出了一种新方法称为 k-Motiflets，将 motif discovery 颠倒了过来，使用基于 k 个重复片段的算法来避免繁杂、不可预知的规则，此外还有自动确定输入参数的扩展功能。实现了无需先验知识就能提取有意义的 motif sets，与现有状态下的四种算法比较，发现本文所提出算法具有（a）数量上更好的相似度，可以找到更大的 motif set；（b）质量更佳，可以导致更清晰、更易解释的 motif，（c）具有最短的运行时间。

    Jun, 2022

  • 同态映射是计算小子图的好基础

    介绍一类称为 Graph Motif Parameters 的图参数，介绍如何根据这个框架更快地计算固定大小的子图在大图中的个数，以及针对一类这样的参数进行问题的复杂度二分，其中包括用于颜色保留的子图计数。

    May, 2017

  • 图的列表染色计数的相关性衰减和确定性 FPTAS

    提出了一种确定性算法，用于大致计算图的列表着色数量及离散马尔可夫随机场模型的分区函数，该算法基于统计物理学中的相关性衰减现象，并且不需要最强的计数技术。

    Jun, 2006