巨圖中三角子圖數的快速計算及其應用

Triangle Counting in Large Sparse Graph

蔡孟宗(Meng-Tsung Tsai)

指導教授 ： 劉邦鋒

共同指導教授 ： 徐讚昇(Tsan-sheng Hsu)

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01523

摘要

在論文中，
我們發展了新的演算法來計算給定圖的三角子圖數。
目前已知最有效率的撥結點演算法需要$O(m^{3/2})$
基本指令的計算時間及$Theta(m)$記憶體空間。
結合廣為人知的四蘇聯人演算法，
可以得到稍微進一步的演算法需要$O(m^{3/2}/log^{1/2}m)$
群聚指令的計算時間及$Theta(m)$記憶體空間。
然而僅有部份的中央處理器支援群聚指令，
在有支援的情況下，
群聚指令被視為基本指令，
在不支援的情況下，
群聚指令可以用$O(log^{(2)}g)$個基本指令完成。
在這論文提到的計算三角子圖中，
並不需要知道每個群聚指令的執行結果。
利用這個特性，
我們發展了攤還式演算法，
它能進一步改善了在不支援的情況下，
群聚指令所需的基本指令僅須$o(log^{(3)}g)$個指令完成。
不管在理論分析或是實驗數據上，
我們的攤還式演算法均勝出，
快的幅度是$omega(log^{1/2}m/log^{(4)}m)$。

關鍵字

三角子圖計算 ； 稀疏圖 ； 高效演算法 ； 群聚指令 ； 除頻原則

並列摘要

In this paper, we develop a new algorithm to count the number of triangles in a graph $G(n, m)$.
The latest efficient algorithm, Forward Algorithm, needs $O(m^{3/2})$ basic instructions' execution time
and $Theta(m)$ memory space.
With the combination of the well-known Four-Russians' Algorithm, we obtain an algorithm that requires
$O(m^{3/2}/log^{1/2} m)$ execution of the population count procedure using $Theta(m)$ memory space.
Some CPUs support population count directly.
In such cases, the population count can be executed with one instruction;
otherwise, an alternative method should be employed.
The known best one is named as extit{bitwise twiddling} method,
which can be executed with $Theta(log^{(2)}g)$ basic instructions.
Owing to it is not necessary to exactly know the result of each population count, we can replace
each population count with an amortized population count.
Therefore, we also develop an efficient algorithm to fast execute the amortized population count.
Based on the theoretic analysis, we conclude that the amortized population count can be executed with
$o(log^{(3)}g)$ basic instructions.
Besides, the experiment result also shows the performance of our amortized population count is better
than others.
As a result, our triangle counting algorithm is faster than the previous known best one by
a factor $omega(g^{1/2} / log^{(3)} g)$ where $g = Omega(log m)$.

並列關鍵字

triangle counting ； sparse graph ； efficient algorithm ； population counting ； frequency division principle

參考文獻

[1]Deepayan Chakrabarti and Christos Faloutsos.

Graph mining: Laws, generators, and algorithms.

ACM Comput. Surv., 38(1), 2006.

[2]Volker Strassen.

Gaussian elimination is not optimal.