【Orca】Orca - Graphlet 和 Orbit 计数算法
Orca（ORbit Counting Algorithm）是一种用于对网络中的小图进行计数的有效算法。它计算网络中每个节点的节点和边缘轨道（4 节点和 5 节点小图）。
orca是一个用于图形网络分析的工具，主要用于计算图中的 graphlets（图形子结构）和 orbits（轨道）。
-
主要功能：
- 计算图中的 graphlets（小型子图模式）
- 分析节点或边的轨道（orbits）
- 用于复杂网络的结构分析
-
具体用途：
- 网络特征提取：帮助理解网络的局部结构特征
- 网络比较：可以用来比较不同网络的结构相似性
- 节点角色分析：分析网络中节点的局部拓扑结构
-
两种分析模式：
node：分析节点的轨道特征edge：分析边的轨道特征
-
Graphlet 大小：
4：分析 4 个节点构成的子图模式5：分析 5 个节点构成的子图模式
举个例子：
- 在社交网络分析中，可以用它来发现网络中的特殊结构模式
- 在生物网络中，可以用来分析蛋白质相互作用网络的结构特征
关于ORCA (Orbit Counting Algorithm) 的重要文献和资源：
-
主要论文：
- 标题：A combinatorial approach to graphlet counting1
- 发表于：Bioinformatics 期刊
- 作者：Tomaz Hocevar 和 Janez Demsar
- 这篇论文详细介绍了 ORCA 算法的原理和实现
-
算法特点：
- 比传统方法快一个数量级
- 专门用于计算图中的 graphlets 和 orbits
- 支持 4 节点和 5 节点的 graphlet 分析
-
扩展研究：
- 还有一篇后续论文：Combinatorial algorithm for counting small induced graphs and orbits3
- 这篇论文进一步扩展了算法的应用范围
-
代码实现：
- 在 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 需要四个参数：
- orbit type: 选择
node或edge - graphlet size: 选择
4或5 - input file: 输入图文件的路径
- output file: 输出文件的路径
例如，如果你要分析节点轨道，使用大小为 4 的 graphlet，命令应该是：
orca.exe node 4 input_graph.txt output_graphlets.txtreference: Orca - Graphlet 和轨道计数算法 |代码海洋
Combinatorial algorithm for counting small induced graphs and orbits | PLOS ONE
combinatorial approach to graphlet counting | Bioinformatics | Oxford Academic