An Experimental Evaluation of a Bounded Expansion Algorithmic Pipeline

摘要: Previous work has suggested that the structural restrictions of graphs from classes bounded expansion--locally dense pockets in a globally sparse graph--naturally coincide with common properties real-world networks such as clustering and heavy-tailed degree distributions. As such, fixed-parameter tractable algorithms for expansion may offer promising framework network analysis where other approaches have struggled to scale. However, there been little done implementing evaluating performance these structure-based algorithms. To this end we introduce CONCUSS, proof-of-concept implementation generic algorithmic pipeline expansion. In particular, focus on using CONCUSS subgraph isomorphism counting (also called motif or graphlet counting), which used extensively tool analyzing biological social networks. Through broad set experiments first evaluate interactions between implementation/engineering choices at multiple stages their effects overall run time. From there, establish viability by demonstrating some scenarios achieves times competitive popular algorithm does not exploit graph structure. Finally, empirically identify two particular ways future theoretical advances could alleviate bottlenecks pipeline.