任何归一化（不）相似度矩阵都可以转换为无向图（加权或不加权）的邻接矩阵。对于未加权的图，您需要根据经验为其邻接矩阵设置阈值，即在两个节点之间发生连接的最小相似度值。对于图的给定分区，模块化度量将量化其集群的总强度，因此通过最大化模块化，您可以获得与该图（集群）相对应的最佳社区结构。

要回答您的问题：

• 只要您的相似度矩阵是对称的，所讨论的图将是无向的。
• 权重（如果存在）是归一化的相似度值。

模块化函数基本上是 NP-hard 组合问题的目标函数。有很多（元）启发式算法可以完成这项任务，如果我没记错的话，谱聚类中使用的归一化切割算法就是其中之一。我没有使用 Chameleon 的经验，但是最大化集群内相似性同时最小化集群间相似性的概念在模块化优化中是相同的。

不幸的是，没有包（我知道）可以自动进行邻接矩阵转换，因为找到最佳阈值是一个手动过程。然而，一旦你有了那个矩阵，R 和 Mathematica 就有很好的软件包来完成剩下的工作。

标准Chameleon使用非对称 k-NN 算法进行初始化，其中参数可以固定为足够大的数字，例如或从数据集大小派生，例如。$k$$10$$k=\sqrt{n}$

和之间的边权重设置为，其中距离定义为欧几里得距离（或任何其他符合三角不等式的距离）。该图没有方向。$A$$B$$w(e) = dist(A,B)$

作者建议对称 k-NN 也可用于图初始化（当点 A 有另一个点 B 作为近邻但点 B 没有点 A 作为近邻时，则不创建边）。然而，由于其高计算复杂性，通常不使用这种方法。

Lesna, Shatovska提出了一些对称 k-NN 的实验。

拥有简单的数据集：

你从 k-NN 创建一个图：

分区后，图形将大大简化（在乞求时具有较大可能根本没有任何影响，因为在分区期间将删除大部分边）。$k$