D 的个人博客

全职做开源,自由职业者

  menu

为博客生成标签图

图是由节点和边组成的。下图是一个 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

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

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

参数

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

杂乱的标签图 

目前我的参数是调整为:WEIGHT = 12SCALE = 10(具体参数含义请参考源代码),效果如下:

我的博客

(实际效果在这里

完整代码