小编Rom*_*ski的帖子

我是Python的新手,我正在尝试根据Python中的这个等式计算页面排名向量:

其中Pi(k)是k-Th迭代后的Page-rank向量,G是Google矩阵,H是超链接矩阵,a是悬空节点向量,α = 0.85,e是1的向量.

使用G进行计算需要花费大量时间,而使用超链接矩阵H(稀疏矩阵)应该花费更少的时间.

这是我的代码:

for i in range(1, k_steps+1):
  for j in range(0, len(dictionary_urls)):
    for k in range(0, len(dictionary_urls)):
        if matrix_H[k][j] != 0:
            matrix_pi_k[i][j] += matrix_pi_k[i-1][k] * float(matrix_H[k][j])
        alpha_pi_k_a += matrix_pi_k[i-1][k]*float(vector_a[k])

    alpha_pi_k_a = alpha_pi_k_a * float(alpha)
    alpha_pi_k_a = alpha_pi_k_a + float((1- alpha))
    alpha_pi_k_a = alpha_pi_k_a / float(len(dictionary_urls))
    matrix_pi_k[i][j] = matrix_pi_k[i][j] * float(alpha)

    matrix_pi_k[i][j] = matrix_pi_k[i][j] + float(alpha_pi_k_a)
    alpha_pi_k_a = 0

k_steps是所需的迭代次数.

dictionary_links包含所有URL.

代码执行后,matrix_pi_k应该具有所有Pi向量 …

我想在具有超过1.5M顶点的图形中计算聚类系数.

我有一个Dictionary顶点ID作为键,值是a 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分钟的时间内计算出该图的聚类系数.

我错过了什么？