Beyond 'Caveman Communities': Hubs and Spokes for Graph Compression and Mining

摘要: Given a real world graph, how should we lay-out its edges? How can compress it? These questions are closely related, and the typical approach so far is to find clique-like communities, like `cavemen graph', them. We show that block-diagonal mental image of graph' wrong paradigm, in full agreement with earlier results graphs have no good cuts. Instead, propose envision as collection hubs connecting spokes, super-hubs hubs, on, recursively. Based on idea, Slash Burn method (burn slash remaining graph into smaller connected components). Our view point has several advantages: (a) it avoids `no cuts' problem, (b) gives better compression, (c) leads faster execution times for matrix-vector operations, which back-bone most processing tools. Experimental our consistently outperforms other methods all datasets, giving compression running time.