【Orca】Orca - Graphlet 和 Orbit 计数算法

Orca（ORbit Counting Algorithm）是一种用于对网络中的小图进行计数的有效算法。它计算网络中每个节点的节点和边缘轨道（4 节点和 5 节点小图）。

orca是一个用于图形网络分析的工具，主要用于计算图中的 graphlets（图形子结构）和 orbits（轨道）。

1. 主要功能：

   • 计算图中的 graphlets（小型子图模式）
   • 分析节点或边的轨道（orbits）
   • 用于复杂网络的结构分析

2. 具体用途：

   • 网络特征提取：帮助理解网络的局部结构特征
   • 网络比较：可以用来比较不同网络的结构相似性
   • 节点角色分析：分析网络中节点的局部拓扑结构

3. 两种分析模式：

   • node：分析节点的轨道特征
   • edge：分析边的轨道特征

4. Graphlet 大小：

   • 4：分析 4 个节点构成的子图模式
   • 5：分析 5 个节点构成的子图模式

举个例子：

• 在社交网络分析中，可以用它来发现网络中的特殊结构模式
• 在生物网络中，可以用来分析蛋白质相互作用网络的结构特征

关于ORCA (Orbit Counting Algorithm) 的重要文献和资源：

1. 主要论文：

   • 标题：A combinatorial approach to graphlet counting1
   • 发表于：Bioinformatics 期刊
   • 作者：Tomaz Hocevar 和 Janez Demsar
   • 这篇论文详细介绍了 ORCA 算法的原理和实现

2. 算法特点：

   • 比传统方法快一个数量级
   • 专门用于计算图中的 graphlets 和 orbits
   • 支持 4 节点和 5 节点的 graphlet 分析

3. 扩展研究：

   • 还有一篇后续论文：Combinatorial algorithm for counting small induced graphs and orbits3
   • 这篇论文进一步扩展了算法的应用范围

4. 代码实现：

   • 在 Code Ocean 平台上有完整的实现和示例2
   • 包含了详细的使用说明和示例数据
   • 该项目提供了软件，用于轻松复制 PLOS ONE （https://doi.org/10.1371/journal.pone.0171428） 中发布的用于计算小诱导图和轨道的论文组合算法的结果。该界面提供三种类型的实验：

• 计数 （） 计算给定网络中 k 节点（k=4 或 5）小图形的轨道。orbit counts 在 output file 中提供。run.sh "Count" k networkorbits.txt

• 比较 （） 将 Orca 对节点和边缘轨道进行计数的速度与暴力枚举进行比较。用于复制表 2 和表 3。请参阅 中报告的执行时间。run.sh "Compare" krun.sh "Compare" "4"run.sh "Compare" "5"Output

• 绘图 （） 运行实验并绘制一个图来说明多项式时间复杂度，如图 9 所示。run.sh "Plot"plot.png

orca.exe [orbit type] [graphlet size] [input file] [output file] 参数说明： 
1. orbit type: - node: 计算节点轨道 - edge: 计算边轨道 
2. graphlet size: - 4: 使用4节点的graphlet - 5: 使用5节点的graphlet 
3. input file: - 输入图文件格式：每行两个数字，表示一条边的两个端点 - 节点编号从0开始 
4. output file: -输出文件包含轨道计数结果

示例输入文件格式：

0 1  
1 2  
2 3  
3 0

这表示一个四边形图，有四个节点（0-3）和四条边。

orca.exe 需要四个参数：

1. orbit type: 选择 node 或 edge
2. graphlet size: 选择 4 或 5
3. input file: 输入图文件的路径
4. output file: 输出文件的路径

例如，如果你要分析节点轨道，使用大小为 4 的 graphlet，命令应该是：

orca.exe node 4 input_graph.txt output_graphlets.txt

reference: Orca - Graphlet 和轨道计数算法 |代码海洋

Combinatorial algorithm for counting small induced graphs and orbits | PLOS ONE

combinatorial approach to graphlet counting | Bioinformatics | Oxford Academic