社群或社区是这样一种组结构，社群内的边密度要高于社群间边密度。即社群内部的节点之间的连接相对紧密，各社群之间的连接相对来说比较稀疏。在社会网络分析中，社区经常被看作是一些凝聚子结构，如派系、群、组、块等。社群主要分为重叠社群图和划分社群图两类，其中后者是把网络中社区结构的发现看作是对整个网络的划分，目前已经有不少成熟的算法实现。社群发现的过程实际上是一个节点群组过程，许多方法都离不开聚类方法。

随机漫步是一种数学统计模型，它是一连串的轨迹所组成，其中每一次都是随机的，它能用来表示不规则的变动形式，通常假设随机漫步是以马尔可夫链或马可夫过程的形式出现的。随机漫步社群发现的思想是假设一漫步者在一个社区（图）里随机游走，漫步者可能被困在连接稠密的区域里（想象一下初次进入一个道路错综复杂的街区），漫步者很容易被“困”（trapped）在里面，这个稠密区域就是漫步者发现的社群。根据图的属性，定义节点和社群之间的结构相似度进行度量漫步者的“行为”，这种相似度是一种可计算的、高效的距离相似度，这样就可以利用合并层次聚类方法建立社区的层次结构，也就是社区结构。可以利用从i点走向（连接，边）j点的概率定义距离相似度（概率距离），若i和j在同一社群里，概率相对比较高。这种算法最坏情况下的计算复杂度为O(mn^2)，m为图的边，n为图的节点。

在R:package:igraph的随机漫步社群发现函数为walktrap.community(……)。在我的人人网好友关系网络进行随机漫步社区发现计算，发现5个社群，其中两个比较密集，代表不同的同学群体。整体效果是非常符合实际的。