Community detection in real-world graphs presents a number of challenges. First, even if the number of detected communities grows linearly with the graph size, it becomes impossible to manually inspect each community for value added to the application knowledge base. Mining for communities with query nodes as knowledge priors could allow for filtering out irrelevant information and for enriching end-users knowledge associated with the problem of interest, such as discovery of genes functionally associated with the Alzheimer's (AD) biomarker genes. Second, the data-intensive nature of community enumeration challenges current approaches that often assume that the input graph and the detected communities fit in memory. As computer systems scale, DRAM memory sizes are not expected to increase linearly, while technologies such as SSD memories have the potential to provide much higher capacities at a lower power-cost point, and have a much lower latency than disks. Out-of-core algorithms and/or databaseinspired indexing could provide an opportunity for different design optimizations for query-driven community detection algorithms tuned for emerging architectures. Therefore, this work addresses the need for query-driven and memory-efficient community detection. Using maximal cliques as the community definition, due to their high signalto-noise ratio, we propose and systematically compare two contrasting methods: indexed-based and out-of-core. Both methods improve peak memory efficiency as much as 1000X compared to the state-of-the-art. However, the index-based method, which also has a 10-to-100-fold run time reduction, outperforms the out-of-core algorithm in most cases. The achieved scalability enables the discovery of diseases that are known to be or likely associated with Alzheimer's when the genome-scale network is mined with AD biomarker genes as knowledge priors.
|Original language||English (US)|
|Title of host publication||SIAM International Conference on Data Mining 2014, SDM 2014|
|Editors||Pang Ning-Tan, Arindam Banerjee, Srinivasan Parthasarathy, Zoran Obradovic, Chandrika Kamath, Mohammed Zaki|
|Publisher||Society for Industrial and Applied Mathematics Publications|
|Number of pages||9|
|State||Published - 2014|
|Event||14th SIAM International Conference on Data Mining, SDM 2014 - Philadelphia, United States|
Duration: Apr 24 2014 → Apr 26 2014
|Name||SIAM International Conference on Data Mining 2014, SDM 2014|
|Other||14th SIAM International Conference on Data Mining, SDM 2014|
|Period||4/24/14 → 4/26/14|
Bibliographical noteFunding Information:
This work was supported in part by the DOE SDAVI Institute and the U.S. National Science Foundation (Expeditions in Computing and EAGER programs).