在概率图形模型中,是派系和群集的相同? -- graphs 领域 和 terminology 领域 和 probability-theory 领域 cs 相关 的问题

In Probabilistic Graphical Models, are Cliques and Clusters the same?


简体版||繁體版
0
vote

问题

中文

在Coursera上的视频的帮助下,我正在学习概率图形模型。我在第4周,我认为经常提到派系。但讨论的图形是群集图。群组和群集也是一样的?

英文原文

I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are the cliques and clusters the same?

        
     
     

回答列表

2
 
vote
vote
最佳答案
 

a clique 是一个严格定义的图形的精确部分$ g =(v,e)$;

$ qquad displaystyle c subseteq v text {clique} iff { {u,v } mid u,v 在c,u neq v } subseteqe e $。< / p>

群集更通用,也更具模糊。这是什么 wikipedia 必须说:

群集分析或群集是以相同组中的对象(称为群集)的方式分组一组对象的任务,而不是对其他组中的那些更相似(在某种意义上或其他) (群集)。

所以,群集也是一组节点,这在某种意义上是"密集" 的,具体取决于所使用的度量。但是,虽然它始终清楚添加音符是否增加了一个clique的大小,但它并不总是看起来只看一个集群,无论是更好的一个集群是否添加节点。群集的质量在图上定义。

作为维基百科文章显示,有很多簇的聚类。派系可以被视为其中一个。

 

A clique is a rigorously defined, exact part of a graph $G=(V,E)$;

$\qquad\displaystyle C \subseteq V \text{ is clique} \iff \{ \{u,v\} \mid u,v \in C, u \neq v \} \subseteq E$.

A cluster is more general, but also more nebulous. Here's what Wikipedia has to say:

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So, a cluster also is a set of nodes that is "dense" in some sense, depending on the metric used. However, while is it always clear whether adding a note increases the size of a clique, it's not always clear from looking only at one cluster whether adding a node to it is better; the quality of a clustering is defined on the whole graph.

As the Wikipedia article shows, there are many notions of clustering. Cliques can be seen as one of them.

 
 

相关问题

3  MaxSAT条款可靠性的差异  ( Variance of maxsat clause satisfiability ) 
对于给定的MaxSAT问题,它是琐碎的易于计算所有分配满足的子句的平均数量,或者等效地对随机分配满足的预期子句数。 同样可以计算满足的子句数量的方差?我的意思是一个精确的计算,而不是估计。 一般,哪些时刻易于计算,哪个很难? 我更喜欢普通Maxsat的答案,但也对Max-3-Sat的特殊情况也有兴趣。 ...

2  动态卡游戏算法的复杂性  ( Complexity of dynamic card game algorithm ) 
将以下动态卡游戏与26个红牌的常规甲板和26个黑卡。经销商一个逐一地绘制了未经测试的卡,我们可以让他随时停下来。对于每个绘制的每张红牌,我们获得1美元,为每张黑卡丢失1美元。问题在于找到返回游戏预期值的算法。如果我们分别表示超过$ B $和$ r $分别在甲板上留下的黑色和红卡的数量,游戏的预期价值$ e(b,r)$...

3  贝叶斯网络的目的是什么?  ( What is the purpose of bayesian networks ) 
我已经看过很多关于贝叶斯网络的解释,但我根本无法在代码中围绕他们的使用。所以这是我的三部分问题。 我是我对贝叶斯网的定义吗?贝叶斯网络是一种(视觉上)描绘变量/事件链接的方式以及它们如何相互影响。可以将概率添加到每个节点中以使您更大的意义会发生什么。与AICASE AI相结合,贝叶斯网用于预测AI的行动并告知它应...

-3  M元素随机样本同样可能...(CLRS 5.3-7)? [关闭]  ( M element random sample being equally likely clrs 5 3 7 ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并通过编辑此帖的问题。 关闭 6年前。 ...

6  当我们只有上限的期望时,Chernoff绑定  ( Chernoff bound when we only have upper bound of expectation ) 
如果$ x $是i.i.d的总和。随机变量在$ {0,1 } $和$ e [x] = mu $中占据价值,CHERNOFF绑定告诉我们 $$$$(x geq(1+ delta) mu) leq e ^ { - frac { delta ^ 2 mu} {3}} $$ 所有$ 0&lt; delta...

7  证明指纹  ( Prove fingerprinting ) 
让$ a neq b $是两个整数从间隔$ [1,2 ^ n]。$让$ p $是一个随机的素数,用1 le p le n ^ c。$证明这一点 $$ text {pr} _ {p in mathsf {primes}} {a Equiv b pmod {p} } le c ln(n)/(n ^ ...

24  如何接近垂直棍子挑战  ( How to approach vertical sticks challenge ) 
此问题是从 prokentstreet.com 我们给出了一个整数的数组$ y = {y_1,...,y_n } $代表$ n $行段,以便分段$ i $的端点为$(i,0)$和$ (我,y_i)$。想象一下,从每个段的顶部射到左侧,当它触及另一个段时,这射线会停止,或者它击中y轴。我们构造了一系列N个整数,$...

3  使随机源均匀分布  ( Making random sources uniformly distributed ) 
如何构建输出位0和1的随机源,以$ prob(0)= prob(1)= 0.5 $。我们可以访问其他随机源$ s $,以$ a $或$ b $与独立概率$ prob(a)$和$ prob(b)= 1 - prob(a)$ overs。 如何调整作业的算法,并且不会消耗超过预期的数量 $(prob(a) cdot ...

2  在M / M / 1队列中,服务时间的指数分布是什么意思?  ( In an m m 1 queue what does exponential distribution of service time mean ) 
我正在阅读关于 99887665544330 我们假设新客户根据泊松分发到达,每个客户都需要一段时间到从指数分布中汲取的服务? 我了解基于泊松分布的到达率的意味着什么 - 如果平均每小时10次,你将有9次,6个非常不经常,11个常见等 - 但是是什么这是否意味着服务是指数级的? 这是否意味着,当您为更多客户服务时...

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia ) 
当两个RV的事件被设置时,我正在尝试实施条件概率分布。如果我尝试从真实或分类变量推断概念,以便为我设置令人困惑。在通常的场景中,对于某些分立的RVS, $ X,Y $ ,我们可以使用贝叶斯定理来计算两个"准时" 事件的条件概率: $$ p(y = y | x = x)= frac {p(x = x | y = y...

3  设定平等的确定性和随机通信复杂性  ( Deterministic and randomized communication complexity of set equality ) 
两个处理器$ a,b $ with输入$ a in {0,1 } ^ n $(以$ a $)和$ b in {0,1 } ^ n $ (以美元)想要决定是否$ a = b $。 $ a $不知道$ b $ ups的输入,反之亦然。 a可以发送消息$ m(a) in {0,1 } ^ n $ the $ b...

3  设施位置问题  ( A facility location problem ) 
考虑以下情景。一个城镇中有n个地方的地方,其中占地平为$ l_i $的数量由$ p_i $,$ i in {1, ldots,n} $。我们需要以达到医院的成本最小化的方式在城镇周围放置K医院。 我们基本上努力 $$ min_o( sum_ {i = 1} ^ n p_i time c(d(l_i,o(l_i...

33  菱形糟糕是多么的洗牌?  ( How asymptotically bad is naive shuffling ) 
众所周知,这种"天真" 通过将每个项目与另一个随机选择的一个单独交换的阵列进行洗牌,不正常运行: for (i=0..n-1) swap(A[i], A[random(n)]); 具体而言,由于在$ N $迭代中的每一个中,获得$ N $的选择之一(具有统一概率),通过计算有$ N ^ n $可能的"路...

4  在线生成统一样本  ( Online generation of uniform samples ) 
源提供商品流$ x_1,x_2, dots $。在每步到$ n $我们想要保存一个随机样本$ s_n subseteq {(x_i,i)| 1 le i le n }尺寸$ k $,即$ s_n $应该是统一选择的来自所有$ tbinom {n} {k} $可能的样本。所以在每一步$ n ge k $我们...

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability ) 
我有一个英语字典(文本文件)和2克,3克和4克的频率作为每个单词的开头。我需要编写一种算法,使用给定的单词,基于转换概率计算可能的字谜(必须进入字典)(我的赋值要求我使用此方法)。 我想使用维特比算法,但我不知道它是否是正确的选择。您如何看待模拟退火算法?你能给我任何帮助吗或建议? ...

20  追逐移动目标的算法  ( Algorithm to chase a moving target ) 
假设我们有一个Black-Box $ F $,我们可以查询和重置。当我们重置$ F $时,将状态$ f_s $ f $设置为随机从SET $$ {0,1,...,n - 1 } $$何处的统一选择的元素$修复,已知为ket $ f $。要查询$ F $$,从$$ {0,1,...,n - 1 } $$提供...

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically ) 
所以我最近重新发现了模拟退火,但其他人似乎很清楚的道路。我知道Metropolis-Hastings作为一种采样算法,它创造了一个Markov-Chain,该链条是通过归一化一些功能而产生的分布。意识到您可以使用它来优化许多事物,并且您甚至可以继续拒绝,这是一个很小的飞跃,甚至可以抵制到目前为止你发现的最少值。但是更...

1  有多少前缀代码我们可以找到给定的概率分发?  ( How many prefix code we can find for a given distribution of probability ) 
源发射5个信号S1,S2,S3,S4和S5,其概率如下:1 / 3,1 / 3,1 / 9,1 / 9,1 / 9,1 / 9。我们可以在= {a,b,c}上构建多少前缀代码?有多少种性能(效率)? ...

1  是均匀位字符串的位xor和non_uniform位串均匀?  ( Is the bitwise xor of a uniform bit string and a non uniform bit string uniform ) 
具有两个位字符串 $ x,y y y y {0,1 rick } ^ n $ ,其中 $ x $ 但 $ y $ 不是。 是 $ z = x oplus y $ 统一? ...

0  启发式确定值f,使得概率d / f接近1/2  ( Heuristically determine a value f such that a probability d f approaches 1 2 ) 
我们有一个m个元素的x。我们希望获得具有m致大小的新组x' ñ。 Choose a first element x from X and put it in X' for each element x in (X - X') Let x' the element from X' which is the cl...

1  贝叶斯网络背景下的线性放松是什么? [关闭]  ( What is linear relaxation in the context of bayesian networks ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并阐明编辑此帖的问题。 关闭 6年前。 ...

2  最佳赌博,以最大限度地减少预期的时间达到目​​标收益  ( Optimal wagering to minimize expected time to reach a target payoff ) 
为简单起见,我们以启动量$ s = 1 $开始,我们希望达到目标金额$ t $。为此,我们顺序地下注一定的数量,然后赢得概率$ P $的那些金额,并失去概率1-P $(已知$ P $的数量。我们希望在最低预期的比赛中达到目标金额$ T $。在每个阶段,我们都可以下注不同的数量。为了使期望更简单地计算我们可以假设如果当...

1  统一采样与约束  ( Uniform sampling with constraints ) 
假设一个人想要在有限的字母表上统一地样本一个给定长度的字符串,这是$ w $满足一组结构约束(例如 - "第三个字符必须等于第一个字符和最后一个字符必须等于第二个")。 显而易见的方法是统一样本$ W $,检查约束是否保持并返回它。但是,我正在处理有许多限制的情况,随机字符串满足它们的概率非常低。有没有办法从满足一组...

1  挑战:关闭哈希,线性探测,探头长度1  ( Challenge closing hash linear probing probe length 1 ) 
挑战说,有一个带有错误的哈希算法,如果它到达数组的末尾,则给出了错误,并且没有找到保存元素的空间, 它直接丢弃它(即,它不会尝试将其放在0,1,2 ...上的位置,因为它是正确的) 在散列表中使用闭合散列,线性探测,探头1。 在此测试的可能性是什么,我们发现实现n有一个错误,如果n = 27并且k = 42? 示...

3  返回具有N字符串长度k的随机子集,而仅在最多k上存储  ( Returning a random subset with length k of n strings while only storing at most ) 
这是问题。我写了一个读取stdin字符串的程序,并返回那些字符串的随机子集。提供给程序的唯一其他参数是子集的长度,$ k $。子集必须恰好包含从整个输入集随机均匀选择的$ k $ strings。 如果每个字符串存储在内存中,则很容易执行此操作。 (记忆成比例为n)。问题是如何仅在大多数$ k $字符串存储,并确保输...




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