未加权图的聚类算法 [英] Clustering algorithm for unweighted graphs

问题描述

我的网络基本上是蛋白质网络，具有未加权和无向图。我想对这个图进行聚类，并将这个图分成不相交的聚类。任何1都可以建议聚类算法，我可以将其应用于未加权和无向图的生物网络。

解决方案

几种图分区算法他们使用不同的范式来解决同样的问题。

最常见的是 Louvain的优化纽曼模块化的方法。
在使用Networkx作为图形库的python中，您可以使用社区分割你的图。

最快的图分区使用 Metis 。它基于分层图粗化。

您也有 N-cut 最初设计用于分割图片。

最后，您可以将图使用随机块模型技术。 可以找到非常好的Louvain python实现和几种块模型技术。 nofollow noreferrer>图形工具。

我最喜欢的是后者，速度很快（基于Boost图库），相对容易使用并可调。编辑：请注意，在图形工具中，我们称之为Louvain模块化的确是纽曼的算法， docs are here 。

I am having unweighted and undirected graph as my network which is basically the network of proteins.I want to cluster this graph and divide this graph in to disjoint clusters. Can any 1 suggest clustering algorithms which i can apply on the biological network which is unweighted and undirected graph.

解决方案

Several graph partitioning algorithms exist, they use different paradigm to tackle the same problem.

The most common is the Louvain's method optimizing Newman's modularity. In python using Networkx as graph library you can use community to partition your graph.

The fastest graph partitioning uses Metis. It is based hierarchical graph coarsening.

You also have N-cut originally designed to segment images.

Finally, you can partition graphs using stochastic block-model techniques. A very good python implementation of Louvain and several block-model techniques can be found in Graph-tool.

My favorite is the latter, it is fast (based on the Boost graph library), relatively easy to use and tuneable.

EDIT: Note that in graph-tool, what we call Louvain modularity is indeed Newman's algorithm, the docs are here.

这篇关于未加权图的聚类算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！