为博客生成标签图

2014-07-24 / Tag Graph Algorithm D3.js JSNetworkX JavaScript

图

图是由节点和边组成的。下图是一个 6 节点无向完全图：

边权重

可以把权重是看成是边的属性，可视化时这个属性决定了边的“粗细”，权重大的边粗一些：

节点度

度就是和节点相连的边的数目。例如上图中，每个节点的度都为 5。我们可以把节点度看成是节点的属性，可视化时这个属性决定了节点的“大小”，度大的节点看上去要大一些：

标签图

好了，上面我们简单介绍了图的概念，接下来我们就开始实战吧：为博客生成标签图！标签图反映了博主文章涉猎的范围、偏好、以及这些标签之间的相关性。

标签数据

要生成标签图，我们需要先准备好基础数据。这些数据就是标签，准确地说是每篇文章的标签：

[
    [   
        "一篇文章的标签",
        "弱类型",
        "Latke",
        "B3log Latke",
        "Java",
        "ORM",
        "JSON",
        "Open Source"
    ],
    [ 
        "另一篇文章的标签",
        "Open Source",
        "NetBeans",
        "JSF",
        "PrimeFaces",
        "JDK 8",
        "Java"
    ]
]

这个 JSON 数组很容易就能生成，保存为 data.json 文件。

生成算法

我们把标签作为节点，现在要做的就是把这些节点连起来。节点之间是否存在边，是通过边权重计算得出的：如果权重大于某个常量参数，则认为这两个节点连通，所以现在的重点就是边权重的计算。

边权重值是两个标签同时出现在同一篇文章标签中的次数

比如上面的 data.json 中，Java 和 Open Source 同时出现了两次，那它们之间的边权重就是 2。下面我们简单描述以下算法并给出核心代码：

1. 从 data.json 中读取所有标签，去重复，放到 tagList 中
2. 遍历 tagList，取出两个标签来计算它们之间的边权重

for (int i = 0; i < tagList.size(); i++) {
    final String tag1 = tagList.get(i);
 1for (int j = i + 1; j &lt; tagList.size(); j++) {
 2    final String tag2 = tagList.get(j);
 3
 4    int originalWeight = getWeight(tag1, tag2, tagsArray);
 5
 6    if (originalWeight &gt; WEIGHT) {
 7        int weight = (int) Math.floor(originalWeight / SCALE);
 8        if (weight &gt; 1) {
 9            // 生成 tag1 和 tag2 带权重的边
10            // ....
11        }
12    }
13}

}
private static int getWeight(final String tag1, final String tag2, final JSONArray tagsArray) {

int ret = 0;
 1for (int i = 0; i &lt; tagsArray.length(); i++) {
 2    // 一篇文章的标签数组
 3    final JSONArray tagArray = tagsArray.getJSONArray(i);
 4
 5    // 转成集合
 6    final Set&lt;String&gt; tagSet = new HashSet&lt;&gt;();
 7    for (int j = 0; j &lt; tagArray.length(); j++) {
 8        final String tag = tagArray.getString(j);
 9        tagSet.add(tag);
10    }
11
12    // 如果这篇文章同时出现了 tag1 和 tag2，则权重加 1
13    if (tagSet.contains(tag1) &amp;&amp; tagSet.contains(tag2)) {
14        ret++;
15    }
16}
17
18return ret;

}

这个 naive algorithm 效率很低，不过因为博客标签数据量不大，实际跑下来还能接受（300+ 标签，耗时 20s+）。

可视化

JSNetworkX

JSNetworkX 是 NetworkX 的 JavaScript 版本，目前已经实现了很多常用算法和特性，基于 D3.js。

基本用法请参考这里，前面我们已经生成了带权重的边，而节点度则是放在这里处理的（因为 JSNetworkX 可以方便的计算节点度），文末给出完整代码。

参数

前面我们提到过边权重参数，这个参数是为了控制生成边的数目（权重大的边才有必要进行绘制），否则生成的图可能会是下面这个样子：

目前我的参数是调整为：WEIGHT = 12，SCALE = 10（具体参数含义请参考源代码），效果如下：

（实际效果在这里）