本篇是来自于今年EuroVis的文章[1]，并且是这次会议的最佳论文，作者是来自于AT&T实验室的Howard Karloff等。
这是一篇关于graph的文章，针对的问题是：对于一个点数量庞大的树，如何更好地对树中的点进行聚集。作者从“信息熵”的角度提出了最大信息熵摘要树(Maximum Entropy Summary Trees)的概念，使得点聚集后的树具有最多的信息。首先，作者从“space-filling layout”和“node-link layout”两种布局所具有的优缺点阐述了前处理的必要性。再次，作者定义了一个每一层最多只能有一个聚集点的摘要树(summary tree)。在此基础上，定义了树的信息熵，树中的点越多，树的信息熵越大，树越平衡，树的信息熵越大。
接着作者提出本篇文章最核心的概念—组合信息熵。在组合信息熵的计算中，组合信息熵只和直接儿子节点的信息熵有关，从而奠定了“自底而上”动态规划的基础。提出信息熵和组合信息熵后，作者通过定义“子树”状态和“子森林”状态，给出了一个自底而上的动态规划算法，计算的步骤是自底而上，自左到右依次计算出“子森林”状态和“子树”状态，算法复杂度为O(K^2*n*W)，K：聚集后的节点个数，n：原始树的节点个数，W：节点权值和。由于该动态规划算法不能允许节点权值是非整数值并且权值不能太大从而影响计算复杂度，所以作者在文章的后半段提出了两个改进的“非精确”算法。第一个是通过将节点权值近似到整数，再应用原动态规划算法，使得该算法能够应用于具有浮点权值节点的树；第二个方法使用了作者提出的启发式策略——对相对不重要的节点进行聚集，保留重要节点，这是一种贪心的方法，算法速度快，并且在作者的实验中也取得了不错的效果。
在最后的实验分析部分，作者使用了五组数据，分别是网络文件点击数据，磁盘文件数据等。下图是关于网络文件点击数据的展示结果，从图中我们可以明显看出最大信息熵摘要树（右）能给出更多的信息。
通过比较五组数据的应用结果，可以发现前两种数据能得到的摘要树具有很高的信息熵，从下图可以看出聚集后的图能达到和原图具有几乎相同的信息熵，原因是数据具有较大的倾斜性；而后三种数据比较均匀，得到的摘要树与原图的信息熵有比较大的差距。从实验可以看出：这种方法适用于具有较大倾斜性的数据。
在这篇文章中，作者的主要贡献在于通过引入了”信息熵”，使得图的可视化结果能被定量地比较，为以后图可视化工作提供了一些借鉴，并且基于”信息熵”给出了计算最大信息熵摘要树的算法。
[1] Karloff, Howard, and Kenneth E. Shirley. “Maximum Entropy Summary Trees.” Computer Graphics Forum. Vol. 32. No. 3.
评论关闭。