发帖
雷达卡
摘要翻译：
本文提出了如何压缩稀疏图的问题。通过引入冗余的思想，我们找到了一种度量网络中节点间邻居重叠的方法。我们利用邻居间的重叠，利用对称性和信息量，分析了如何通过收缩网络来减少信息量，并利用我们创建的特定数据结构，将压缩问题推广为轨道选择的优化问题。为了找到一个合理的解决这个问题的方法，我们使用贪婪算法来确定对称性辨识的轨道，实现压缩。文中给出并分析了该算法的一些实例实现。
---
英文标题：
《Graph Compression -- Save Information by Exploiting Redundancy》
---
作者：
Jie Sun, Erik M. Bollt, Daniel ben-Avraham
---
最新提交年份：
2007
---
分类信息：
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
---
英文摘要：
In this paper we raise the question of how to compress sparse graphs. By introducing the idea of redundancy, we find a way to measure the overlap of neighbors between nodes in networks. We exploit symmetry and information by making use of the overlap in neighbors and analyzing how information is reduced by shrinking the network and using the specific data structure we created, we generalize the problem of compression as an optimization problem on the possible choices of orbits. To find a reasonably good solution to this problem we use a greedy algorithm to determine the orbit of symmetry identifications, to achieve compression. Some example implementations of our algorithm are illustrated and analyzed.
---
PDF链接：
https://arxiv.org/pdf/712.3312
京公网安备 11010802022788号
