2016 · 14 citations · 16 references
ComputingComputer ScienceBiomedical Text MiningData StructuresKnowledge RepresentationGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryNetwork StructureCompressionDescription Length PrinciplesGraph DecompositionsMinimum Description LengthStorageSubgraph Extraction
How can we fully structure a graph into pieces of meaningful information? Into structures that provide us with insights and carry a meaning beyond simple clustering. How can we also exploit these patterns to compress the graph for fast transmission and easier storage? In many applications of graph analysis like network analysis or medical information extraction we are searching for special patterns. Here, it is not sufficient to extract only parts of the relevant information in a graph, but to understand the complete underlying structure. Therefore, we propose our algorithm MeGS (Partitioning Meaningful Subgraph Structures using Minimum Description Length) to fully understand how a graph is constructed. The most common primitives (clique, hub, tree, bipartite, and sparse) serve as models to split a graph into meaningful structures. Using the principle of Minimum Description Length (MDL) structure types and counts are determined by the best fitting model. These structures achieve the best compression of the adjacency matrix. As result, every node is part of exactly one structure and has an interpretable context. No unknown areas remain in the graph. The higher a model compresses its section of the graph, the stronger its match with the corresponding structural assumption. MeGS, a fast and parameter-free split-and-merge algorithm, automatically finds the optimal structures achieving the best compression. We compare to state-of-the-art algorithms to prove MeGS' ability for interpretation and compression.
16
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948 · 80.7K citations
Modeling by shortest data description
J. Rissanen · Automatica · 1978 · 6K citations
Paolo Boldi, Sebastiano Vigna · 2004 · 1.2K citations