标签: graph-theory

好吧,我正面临一个即将加入我的家庭,并通过选择姓名.

我考虑过编写软件来显示名称,并强迫我选择哪个更好,类似于小猫战争.

但是,一旦我有了一个巨大的图表,我不知道如何处理它,特别是如果有周期.例如,我比mam更喜欢mike,比jared更好的sam,比mike更好的jared - 简单地分配投票并计算它们是没有意义的(这就是我认为小猫战争所做的事情).此外,我可能有一天会得到迈克与贾里德并以单向投票,但如果我在另一天获得投票,则投票方式也不同.

所以:

• 获得数据后,如何处理图表并对名称进行排名？

交替:

• 可以使用哪些其他有用的算法来做出选择(比如车辆风格,如果你正在寻找新车)？

-亚当

是否存在旅行推销员问题,其中最优解具有交叉边缘？

节点位于xy平面中,因此在这种情况下交叉意味着如果要绘制图形,则连接四个单独节点的两个线段将相交.

是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向的,未加权的图形,我需要找到其中的所有子图,其中子图中的每个节点都连接到子图中的每个其他节点.

是否有现有的算法？

我已经看了很多用于图形布局的包(Graphviz,Gephi,Cytoscape,NetworkX等等,这些都是比较流行的),但它们似乎都没有扩展到这种尺寸.有哪些技术可视化这种尺寸的图形或将它们减少到更易于管理的东西？

我正在做一些研究,我已经达到了计算图形的聚类系数的程度.

根据这篇论文直接与我的研究有关:

聚类系数C(p)的定义如下.假设顶点v具有k _v个邻居; 那么它们之间最多可以存在(k _v*(k _v -1))/ 2个边缘(这发生在v的每个邻居连接到v的每个其他邻居时).设C _v 表示实际存在的这些允许边的分数.将C作为所有v 的C _v的平均值

但这篇关于这个主题的维基百科文章说的不同:

C =(闭合三元组的数量)/(连接的三元组的数量)

在我看来,后者的计算成本更高.

所以我的问题是:它们是否相同？

应该注意的是,该论文被维基百科文章引用.

谢谢你的时间.

我正在使用一些流行的python包作为基础,为图形和网络开发一个开源近似算法库.主要目标是在图形和网络上包含NP-Complete问题的最新近似算法.原因是1)我还没有看到一个很好的(现代)整合软件包来涵盖这个和2)它将是一个很好的教学工具,用于学习NP-Hard优化问题的近似算法.

在构建这个库时,我使用单元测试来进行健全性检查(正如任何适当的开发人员所做的那样).我对我的单元测试有些谨慎,因为它们本质上是近似算法可能无法返回正确的解决方案.目前我正在手工解决一些小实例,然后确保返回的结果与之匹配,但这在实现意义上是不可取的,也不是可扩展的.

单元测试近似算法的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报(测试时间很幸运,并不能保证所有实例都低于限制).

任何人都可以建议我在图论的良好在线教程,即BFS,DFS和其他相关的图形算法？

我理解pagerank背后的想法并实现了它(当阅读"编程集体智慧"一书时).

但我读到它可以分布在几个服务器上(我猜谷歌正在做).我有点困惑,因为根据我的理解,你需要整个图表才能对其进行页面排名,因为每个排名都与其他排名相关.

我发现了维基文章,但没有解释太多.

有关如何做到这一点的任何建议？另外,奖励问题:是否可以将分布式pagerank专用于pagerank,或者将所使用的方法应用于应用于图形的其他机器学习算法？

我正在寻找一种方法来自动将城市中的社区定义为图形上的多边形。

我对邻里的定义有两个部分：

1. 街区：在多条街道之间封闭的区域，其中街道（边）和交叉点（节点）的数量最少为三个（三角形）。
2. 邻域：对于任何给定的街区，与该街区直接相邻的所有街区以及街区本身。

有关示例，请参见此插图：

例如，B4是由 7 个节点和连接它们的 6 个边定义的块。正如此处的大多数示例一样，其他块由 4 个节点和连接它们的 4 条边定义。此外，附近的B1包括B2（反之亦然），而B2还包括B3。

我正在使用osmnx从 OSM 获取街道数据。

1. 使用 osmnx 和 networkx，我如何遍历图来找到定义每个块的节点和边？
2. 对于每个块，我如何找到相邻的块？

我正在努力编写一段代码，该代码以图形和一对坐标（纬度、经度）作为输入，识别相关块并返回该块的多边形以及上述定义的邻域。

这是用于制作地图的代码：

import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt

G = ox.graph_from_address('Nørrebrogade 20, Copenhagen Municipality',
                          network_type='all', 
                          distance=500)

以及我试图找到具有不同节点数和度数的派系。

def plot_cliques(graph, number_of_nodes, degree):
    ug = ox.save_load.get_undirected(graph)
    cliques = nx.find_cliques(ug)
    cliques_nodes = [clq for clq in cliques if len(clq) …

有一组用户。一个人可以拥有多个用户，但ref1和ref2可能相似，因此可以将用户链接在一起。ref1且ref2不重叠，则 中ref1不存在 中的一个值ref2。

一个用户可以拥有多种资产。我想“合并”具有一个或多个相似参考的用户，然后计算他们总共拥有多少资产。用户表中可能缺少条目，在这种情况下，我只想将所有者传播到 ref2 并设置 asset_count 和 asset_ids。

下面是一个示例架构来说明：

示例资产

SELECT * FROM assets;

用户示例

SELECT * FROM users;