对不确定图的可达性查询 -- algorithms 领域 和 graphs 领域 和 probability-theory 领域 和 union-find 领域 cs 相关 的问题

Reachability queries on uncertain graphs


简体版||繁體版
0
vote

问题

中文

我们有一个不确定的图表$ g $,其中每个边缘$(u,v)$存在概率$ p _ {(u,v)} in(0,1] $。我们想要分配得分$ [0,1] $给每对顶点$ U $和$ V $,它表示它们位于同一连接组件中的可能性。

如果唯一可能的分数是离散的$ 0 $和$ 1 $,那么此问题会降低到连接的组件列表或图形到达性问题。在不确定的图表中可以解决这个问题吗?

英文原文

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

           
         
         

回答列表

5
 
vote

我编辑了你的问题,使其自包含。

不确定图表的文献对于这个问题来说真的很丰富。您正在寻找的是"在不确定的图表中可达性" ,它已经广泛在数据库社区中进行了广泛研究[1]。

基本上,您在两个顶点$ U $和$ V $之间的边缘,概率$ p_ {uv} in(0,1] $。您需要找到两个给定顶点是否可到达,因此,位于相同的连接组件 disjoint set 。我建议您看看以下纸张作为起点,它描述了基础知识,可以引导您更多的作品在这个问题上完成:

[1]金,ruoming等。 "在不确定图中的距离约束可达性计算。" VLDB捐赠的程序 4.9(2011):551-562。

 

I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

[1] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." Proceedings of the VLDB Endowment 4.9 (2011): 551-562.

 
 

相关问题

3  为什么工会的时间复杂性 - 查找是$ O(LGN)$只有“outge and等级”?  ( Why time complexity of union find is olgn with only union by rank ) 
我正在研究联盟的时间复杂性 - 找到数据结构。 我看到了工会的时间复杂性,找到功能取决于某些条件。 没有任何东西:$ o(n)$ 与Union排名:$ O( log n)$ 具有路径压缩:$ o( alpha(n))$,它是逆Ackermann函数。 我理解$ o(n)$,因为歪曲的脱节集。但是,我无法理解$...

0  融合两个群集列表的最佳方式  ( Best way to fusion two list of clusters ) 
想象下列: A = Set( sortedSet(1,2,3), sortedSet(4,8)) B = Set( sortedSet(3,4), sortedSet(5,6,7) ) 每个内部列表代表由索引点组成的群集(1,2,3 ...)。 我想收集群集共享与相同索引共享的点,以获取: Set( s...

2  运行时差异贝六联盟由unions的等级和联盟  ( Runtime difference bewteen union by rank and union by size for union find ) 
我正在学习联盟找到,并且根据 wikipedia ,有2种类型Union:Union等级和联盟规模。我的问题是,两个(如果有的话)之间的运行日差异是什么? 直观地,它的感觉逐个尺寸会始终更好,因为每次合并,我们都会在一棵树中增加每个节点的等级1,并最大限度地减少整体运行时,我们希望增加一棵树到是具有较少数量的节点的节...

0  用路径compresson和秩的联盟发现分析  ( Analysis of union find with path compresson and rank ) 
我已经被赋予,$ n $ make-set和$ m ge k $ finds,美元可以在$ o(n + m log ^ *(k))中执行$ k $ neions)$ time(i' m意识到Ackermann功能,但对证明这一点不感兴趣)。如果$ log ^ *(k)$ 2 $ 0 $ if $ k le 1 ...

1  关于Sedgewick and Wayne算法速金的复杂性分析  ( On the complexity analysis of quick union in algorithms by sedgewick and wayne ) 
我目前正在学习算法,第四版Sedgewick等。在第226页,有一个分析了Quick-Union算法的Find()方法最坏的情况。 这是算法: private int find(int p) { // Find component name. while (p != id[p]) p = i...

0  DSU算法优化  ( Dsu algorithm optimization ) 
我们知道DSU(脱节集合)如何用于找到两个用户之间的连接。但是,我想知道它是否可以与段树一起使用。 让我进一步解释我的想法。假设我们有 $ n $ 人,从 $ 1 $ 到 $ n $ 。我有一个输入列表,指定两个人是否是朋友。在数据上运行DSU将告诉我是否有两个人是朋友。轻松简单直到在这里。现在,假设我有一些类型的类...

3  Union的有趣应用  ( Interesting applications of union find ) 
我一直在尝试找到Union的有趣应用 - 发现这是较小的人。以下是基于Union的一些流行的算法 - 找到我知道的: Kruskal的MST 算法 tarjan的离线Loperse祖先(LCA)算法 1 < / li> 解决范围使用Union-Mexing通过减少到LCA查找的范围最小查询(使用[tarjan...

0  对不确定图的可达性查询  ( Reachability queries on uncertain graphs ) 
我们有一个不确定的图表$ g $,其中每个边缘$(u,v)$存在概率$ p _ {(u,v)} in(0,1] $。我们想要分配得分$ [0,1] $给每对顶点$ U $和$ V $,它表示它们位于同一连接组件中的可能性。 如果唯一可能的分数是离散的$ 0 $和$ 1 $,那么此问题会降低到连接的组件列表或图形到达...

4  找到kruskal算法实现最坏情况运行时间的图表  ( Find a graph for which kruskals algorithm achieves worst case running time ) 
我正在研究一个问题,其中我必须在n顶点上找到一个边缘权重的图表,其中kruskal的算法实现了最坏情况的运行时间。我正在使用联盟 - 查找数据结构,但没有优化(路径压缩或权重/高度联合规则)。 kruskal的版本我使用的是如下: Kruskal(G) for each vertex ???? ∈ ????...

1  如何显示连接组件中的两个顶点处于同一组? (BI条件)  ( How to show that two vertices in a connected component are in the same set bi ) 
显示,在通过连接组件处理所有边缘后,如果它们在同一组中,则两个顶点位于相同的连接组件中。 连接组件算法如下: 似乎很明显,当我们继续将连接的部件的直接边缘的顶点添加到一个集合时,最终形成的设置具有连接的部件中的所有顶点 - 直接连接以及间接连接。 但我如何正式证明这一点?这也看起来像是一个奇迹对我来说。 我想到...

0  给定N顶点和M边缘发现两个节点是否在同一连接的组件中?  ( Given n vertices and m edges find if two nodes are in the same connected compone ) 
给定一组 $ n $ 人和 $ m $ 这些人之间的友谊关系(关系我们需要在两个人之间建议一个数据结构,这些数据结构支持那些人分为最大组的数据结构,使得如果连接了2个人,则它们属于同一组。 询问 $ k $ 查询,其中每个查询询问 $(i,j)$ 是2个人在同一组中,数据结构可以具有 $ o(m + n + k)$ ...

6  拆分:维护动态图形连接信息,在边缘删除下  ( Split find maintaining dynamic graph connectivity information under edge delet ) 
是有没有数据结构,以跟踪动态图形的连接组件,当图表可以通过删除图形的边缘来改变图形? 让$ g $是一个无向图。我有两个手术,我希望能够执行: 删除$(u,v)$:从图中删除边缘$(u,v)$。 samecomponent $(u,v)$:根据$ u,v $返回true或false是否在同一连接的组件 上 ...

3  如何了解kruskal的复杂性通过Quick-Union通过等级和路径压缩实现?  ( How to understand the complexity of kruskal implemented with quick union by rank ) 
我正在尝试通过等级和路径压缩使用Quick-Union实现的Kruskal算法的复杂性。 现在存在上面最后一个结构的定理: 粉碎,联合和查找的任何序列的复杂性,其中的 m 操作,其中 n 在Quick Union上的级数是由等级和路径压缩的最坏情况等于$ O(m ,,g(n))$。 $ g(n)$是 ackerma...

1  为什么交换功能在Union找到算法中使用?排名或大小数组如何用于优化  ( Why swap function is use in union find algorithm how rank or size array is used ) 
void union_sets(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) { if (size[a] < size[b]) swap(a, b); pa...

3  快速联合和启发式的大小  ( Quick union and heuristic by size ) 
学习快速查找和快速联合启发式,我发现了: 快速查找树木和工会,基于树的大小我们可以在$ t_ {am}(n)= o( log(n))$ 快速查找树木和一个基于树的高度的工会,我们可以在$ t(n)= o( log(n))$ 中找到一个查找 但是我读到了使用快速联合树和一个联盟基于树的大小我们也可以在$ ...

1  如何分析联合查找加权Quick-Union方法的最坏情况  ( How to analyze the worst case of weighted quick union method on union find ) 
这里是罗伯特Sedgewick和Kevin Wayne的算法中的1.5.15。 表明,用于加权Quick-Union的最坏情况树中每个级别的节点的数量是二项式系数。使用 $ k = 2 ^ $ 节点来计算最坏情况树中节点的平均深度。 以下是我的问题: 1)加权Quick Union的最坏情况树是什么? 2)...

1  为什么不使用root作为直接父级实施联盟 - 查找结构?  ( Why not implement union find structure using root as the direct parent ) 
我刚刚学习了通过等级和路径压缩使用UF。在在节点上调用后,可以通过将节点附加到其根目录通过将节点附加到其根部来压缩路径。如果这里的目标是达到树,为什么不仅仅是实现树,使每个节点直接连接到其根(而不是其真实父级)?这样,从一开始就可以实现最大压缩。只要由排名使用的联盟和它一起使用它是什么? ...

0  苏尔达斯和凯文韦恩算法第四版加权快速联盟的复杂性分析  ( On the complexity analysis of weighted quick union in algorithms 4th edition by ) 
我一直在学习Sedgewick的书,并试图在最坏的情况下计算加权快速联盟的数组访问数。第四版在第229页的左侧有一个图表。 我们从8个站点开始: 0 1 2 3 4 5 6 7 所以n = 8 然后我们形成对: 对于每个对的p>是一个对比较的阵列的一个访问,根据find()方法: private...

1  一个适当的数据结构来表示一系列集合(其支持完全是制作设置(x),Union(S1,S2),报告)  ( An appropriate data structure to represent a family of sets which supports exac ) 
我需要用一些适当的数据结构代表集合的家庭f。数据结构需要支持程序组合(x),脱消联合(a,b)和报告(a)。我没有实施程序本身的问题。如果您遵循关于在算法介绍中介绍的关于算法的章节中介绍的想法(CLRS for Short)章节中介绍的想法非常直接。我的问题是,在本书中,有一个添加的过程查找(x),即给定f的任何成员...

12  联合的复杂性 - 找到路径压缩,没有排名  ( Complexity of union find with path compression without rank ) 
wikipedia通过路径压缩的等级说联盟给出了$ o( log n)$的摊销时间复杂性,并且通过等级和路径压缩的两个工会给出了$ o( alpha(n))的摊销时间复杂性$(其中$ alpha $是Ackerman函数的倒数)。但是,它没有提及路径压缩的运行时间,没有联盟等级,这是我通常实现自己的。 如何通过路...

12  定向工会 - 查找  ( Directed union find ) 
考虑一个指示的图表$ g $,其中一个可以动态地添加边缘并制作一些特定的查询。 示例:脱节集森林 考虑以下一组查询: arrow(u, v) equiv(u, v) find(u) 第一个添加箭头$ u→v $ the图表,第二个一个决定$u∈^ * v $,最后一个找到了$↔^ * $的等价类别的规范代表...

1  难度少数步骤证明“$ 文本的摊销成本{find-set} $操作是$ theta( alpha(n))$”假设联合按等级,路径压缩  ( Difficulty in few steps in proof of amortized cost of textfind set operati ) 
我正在读取数据结构的剖面集从文本对算法引言 by cormen等。 AL 。我难以理解在问题标题中给出的错误证明少数步骤。 在这里,我们假设我们按照等级和路径压缩启发式遵循联盟。在我们进入我们的目标引发之前,需要一些定义和引理作为目标引理的先决条件。 ( note :下面是我面临难度的证据的先决条件;由于证明是指...

1  这意味着一组间隔由右侧和左终点排序?  ( What does it mean that a set of intervals is sorted by the right and left endpoi ) 
读取纸张(在间隔的K色)上,我介绍了以下描述: "输入:一个整数k,以及由右端点和左端排序的一组n间隔。按照右端点的顺序索引间隔,并且假设所有端点都是正整数。" 是什么意思,它们被"右端和左端点" 排序?这是否意味着每个间隔都在表单上(左端点,右端点)? ...

1  为什么下限为此制作,Union和查找设置序列的下限$ M log n $?  ( Why is the lower bound m log n for this make set union and find set sequence ) 
查看此解决方案: 是下限$ m log n $,因为我们只是仅通过等级查看Union的下限?如果我们制作$ N $ Make-Set操作,那么将有$ log n $ union操作,然后是$ m - 2n + 1 $查找设置操作。对我来说,下限似乎更大,但我缺少了什么? ...

0  在不相交的集合中测试成员资格的复杂性  ( Complexity of testing membership in a disjoint set ) 
我有一个脱节集数据结构(有时称为union-find数据结构),其中我在每个"节点" 中存储一个值。我想按值查找节点。我该怎么办? 通常在文献中讨论的表示,链接列表和森林,处理被给出的节点(链接列表或森林)的操作,而不是其中包含的值,这避免了由于必须找到包含一个节点而导致的任何困难给定价值。从我所看到的,给定的脱编集...

相关问题

3  为什么工会的时间复杂性 - 查找是$ O(LGN)$只有“outge and等级”? 
0  融合两个群集列表的最佳方式 
2  运行时差异贝六联盟由unions的等级和联盟 
0  用路径compresson和秩的联盟发现分析 
1  关于Sedgewick and Wayne算法速金的复杂性分析 
0  DSU算法优化 
3  Union的有趣应用 
0  对不确定图的可达性查询 
4  找到kruskal算法实现最坏情况运行时间的图表 
1  如何显示连接组件中的两个顶点处于同一组? (BI条件) 
0  给定N顶点和M边缘发现两个节点是否在同一连接的组件中? 
6  拆分:维护动态图形连接信息,在边缘删除下 
3  如何了解kruskal的复杂性通过Quick-Union通过等级和路径压缩实现? 
1  为什么交换功能在Union找到算法中使用?排名或大小数组如何用于优化 
3  快速联合和启发式的大小 
1  如何分析联合查找加权Quick-Union方法的最坏情况 
1  为什么不使用root作为直接父级实施联盟 - 查找结构? 
0  苏尔达斯和凯文韦恩算法第四版加权快速联盟的复杂性分析 
1  一个适当的数据结构来表示一系列集合(其支持完全是制作设置(x),Union(S1,S2),报告) 
12  联合的复杂性 - 找到路径压缩,没有排名 
12  定向工会 - 查找 
1  难度少数步骤证明“$ 文本的摊销成本{find-set} $操作是$ theta( alpha(n))$”假设联合按等级,路径压缩 
1  这意味着一组间隔由右侧和左终点排序? 
1  为什么下限为此制作,Union和查找设置序列的下限$ M log n $? 
0  在不相交的集合中测试成员资格的复杂性 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有