问题标签 [adjacency-matrix]

我正在使用邻接矩阵来表示可以在视觉上解释为的朋友网络

使用这个矩阵，我想编译一个所有可能的友谊三角形的列表，条件是用户 1 是用户 2 的朋友，用户 2 是用户 3 的朋友。对于我的列表，不需要用户 1 是朋友用户 3。

我有一些代码可以很好地处理小三角形，但我需要它来扩展非常大的稀疏矩阵。

我能够在大约 21 分钟内在 csr_matrix 上运行代码。该矩阵为 1032570 x 1032570，包含 88910 个存储元素。总共生成了 2178893 个三元组。

我需要能够对 1968654 x 1968654 稀疏矩阵和 9428596 个存储元素做类似的事情。

我对 python 非常陌生（不到一个月的经验），并且在线性代数方面不是最好的，这就是为什么我的代码没有利用矩阵运算的原因。任何人都可以提出任何改进建议或让我知道我的目标是否现实？

所以我已经为此工作了几个小时，我非常沮丧。我不明白我做错了什么。

我正在使用 Dijkstra 算法来查找源顶点与使用邻接矩阵的其他 4 个顶点之间的最短路径。这背后的想法是有 5 个城市和往返它们的航班，我需要找到最便宜的机票价格，同时考虑到中转时间。

我正在遵循我书中的算法，这是伪代码，以及以下网站上的代码：http: //vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in- c-2/

我遇到的问题是，在网站上的嵌套 for 循环中，计数器 i 从 1 开始，我相信这就是为什么从源顶点到所有顶点的距离都是正确的，除了第一个不变为 999。

例子：

当前距离：999 220 0 115 130

前辈：0 3 0 2 2

所有这些距离都是正确的——即使我改变了源顶点——除了第一个保持不变。

如果我将计数器 i 更改为 0，它会在每一个距离上都搞砸，即

当前距离：0 105 0 0 0

无论如何，请帮助。这是相关的代码。

我为不同大小的有向图创建了邻接矩阵。我有大约 30,000 个矩阵，每个矩阵都在一个单独的文本文件中。我如何对它们进行集群，是否有可用的工具。表示用于聚类的有向图的最佳方法是什么。

谢谢你。

我正在做一个关于 Facebook 网络社交网络分析的项目。我必须让我所有的朋友和我的朋友中的谁是彼此的朋友，在我的网络中建立相互的友谊。我这样做了，我得到了我的朋友和邻接的所有 id，现在我必须形成一个邻接矩阵，表明我的 2 个朋友是否是朋友。例如：A和B是朋友，A和C是朋友，但B和C不是朋友。这看起来像这样：

因为我已经在 python 中有 id 和邻接的列表，我也应该在 python 中做矩阵，所以如果你有任何想法或基本算法如何输入 1 和 0，我将不胜感激。

我试图弄清楚 BFS 如何是 O(m+n)，其中 n 是顶点数，m 是边数。

算法是：

在邻接列表中，我们将顶点存储在数组/哈希表中，以及每个顶点与其他顶点形成的边的链表。

我的主要问题是：我们如何实现获取未访问的子节点？很明显，您将节点标记为已访问，但是在遍历时，您会遍历所有链表，因此您将每条边计算两次，所以复杂度是 O(2m+n) 对吧？这是否只是四舍五入到O（m + n）？

另外，我们可以对邻接矩阵采用类似的策略吗？如果给定一个大小为 nxn 的矩阵，并且我想知道是否存在特定元素，我可以做一个 BFS 来解决这个问题吗？

谢谢。

X 是一个文本文件，包含100000相同大小（500 个元素）的位向量（即每行是一个包含 500 个元素的向量）。我正在使用下面的代码生成一个邻接矩阵（100000 X 100000），但它没有优化并且非常耗时。我该如何改进。

谢谢你。

是否可以在 Neo4j 中获得图的邻接矩阵？还是我需要自己构建它？

谢谢！

这是我用于 Kruskal 算法的伪代码。我在这里使用的数据结构是邻接矩阵。我得到了增长的顺序n^2。我想知道它是否正确。

我需要计算矩阵的 3 和 4 次方的轨迹，并且它需要尽可能快。

这里的矩阵是一个简单图的邻接矩阵，因此它是正方形的，对称的，它的元素总是 1 或 0，对角元素总是 0。

对于矩阵的 2 次幂的轨迹，优化是微不足道的：

• 我们只需要跟踪的对角线条目 (i,i)，跳过所有其他
• 由于矩阵是对称的，这些条目只是第 i 行的条目平方和相加
• 由于条目只有 1 或 0，因此可以跳过平方运算

我在维基百科上找到的另一个想法是总结 Hadamard 产品的所有元素，即逐项乘法，但我不知道如何将此方法扩展到 3 和 4 的幂。

请参阅http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties

也许我只是盲人，但我想不出一个简单的解决方案。

最后我需要一个 C++ 实现，但我认为这对这个问题并不重要。

提前感谢您的帮助。

我有一个表示加权有向图边缘的三元组（顶点1、顶点2、权重）列表。由于原型实现是在 Matlab 中进行的，因此这些被导入为 Nx3 矩阵，其中 N 是边数。所以这个天真的实现是

tribbles 的问题是“id1”和“id2”是不连续的；它们是代码。这给了我三个问题。(1) 具有太多“幻像”、虚假顶点的巨大矩阵，这会扭曲与该矩阵一起使用的算法的结果；(2) 我需要恢复所述算法结果中的代码（可以这么说如果连续 1:m 的 id 代码是微不足道的）。

Matlab 中的答案是可取的，但我认为我可以从其他语言的答案中破解（只要它们不是“R 具有执行此操作的库”之类的预打包解决方案）。

我是 StackOverflow 的新手，我希望尽快为社区做出有意义的贡献。暂时先谢谢了！

编辑：如果我们在多个顶点的原点没有顶点，这将是一个解决方案。（这意味着边源列表和身份列表之间存在 1:1 匹配）