c# - 聚类系数 C#

Question

我想计算具有超过 150 万个顶点的图中的聚类系数。

我有一个以顶点 ID 作为键的 Dictionary，值是一个 List，其中包含连接到顶点 ID 的所有顶点。

聚类系数 = 3 * 三角形/连接的三元组数。

问题是:计算图中三角形的数量需要 4 个多小时。

我的代码:

List<string> list_t = new List<string>();
Dictionary<string, List<string>> copy = new Dictionary<string, List<string>>(Global.dict_edge_undirected);
int triangles = 0;                          // (number of triangles in graph)*3
foreach (KeyValuePair<string, List<string>> pair in copy)
{
    if (pair.Value.Count > 1)
    {
        foreach (string neigh1 in pair.Value)
        {
            list_t = copy[neigh1];
            foreach (string neigh2 in pair.Value)
            {
                if (neigh1 != neigh2 && list_t.Contains(neigh2))
                {
                    triangles++;

                }
            }
        }
    }
}

如何减少运行时间？

C++ igraph 库在不到 3 分钟的时间内计算出该图的聚类系数。

我错过了什么？

Answer 1

您可以使用 HashSet<T>而不是至少列出:

        var copy = new Dictionary<string, HashSet<string>>(Global.dict_edge_undirected);
        int triangles = 0;                          // (number of triangles in graph)*3
        foreach (var pair in copy)
        {
            if (pair.Value.Count > 1)
            {
                foreach (string neigh1 in pair.Value)
                {
                    triangles += pair.Value.Count(neigh2 => neigh1 != neigh2 && copy[neigh1].Contains(neigh2));
                }
            }
        }

它删除了一个内循环，因为 Contains哈希表的方法是 O(1)。

第二 - 你可以使用 int ID 而不是字符串(并使用 Dictionary<int,string> 或简单的 string[] 来按 ID 获取字符串)。它将删除具有相同哈希码的字符串的额外比较。在这种情况下你不需要使用字典，你可以只使用一个数组:

        const int N = 100;
        var copy = new HashSet<int>[N];
        int triangles = 0;                          // (number of triangles in graph)*3
        foreach (var pair in copy)
        {
            if (pair.Count > 1)
            {
                foreach (int neigh1 in pair)
                {
                    triangles += pair.Count(neigh2 => neigh1 != neigh2 && copy[neigh1].Contains(neigh2));
                }
            }
        }

所有数组操作都由 JIT 优化。

最后，你可以使用Parallel提高性能(局部变量用于最小化 Interlocked.Add 调用)

        int totalTriangles = 0;
        Parallel.ForEach(copy, () => 0,
                         (set, _, __) =>
                         {
                             int triangles = 0;
                             if (set.Count > 1)
                             {
                                 foreach (int neigh1 in set)
                                 {
                                     triangles += set.Count(neigh2 => neigh1 != neigh2 &&
                                                                      copy[neigh1].Contains(neigh2));
                                 }
                             }
                             return triangles;
                         },
                         i => Interlocked.Add(ref totalTriangles, i));

或使用 PLINQ:

const int N = 100;
var copy = new HashSet<int>[N];
int triangles = copy.AsParallel().Where(pair => pair.Count > 1).Sum(pair => pair.Sum(neigh1 => pair.Count(neigh2 => neigh1 != neigh2 && copy[neigh1].Contains(neigh2))));