GUAN Bo, ZAN Xiangzhen, XIAO Biyu, MA Runnian, ZHANG Fengyue, LIU Wenbin. Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient[J]. Chinese Journal of Electronics, 2013, 22(3): 517-520.
Citation: GUAN Bo, ZAN Xiangzhen, XIAO Biyu, MA Runnian, ZHANG Fengyue, LIU Wenbin. Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient[J]. Chinese Journal of Electronics, 2013, 22(3): 517-520.

Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient

Funds:  This work is supported in part by the National Natural Science Foundation of China (No.61272018, No.60970065, No.30970666 and No.61174162), the Natural Science Foundation of Zhejiang Provincial (No.R1110261), and Xinmiao Foundation (No.2012R424051) by the Science and Technology Department of Zhejiang Province.
  • Received Date: 2012-04-01
  • Rev Recd Date: 2012-12-01
  • Publish Date: 2013-06-15
  • Densely connected patterns in biological networks can help biologists to elucidate meaningful insights. How to detect dense subgraphs effectively and quickly has been an urgent challenge in recent years. In this paper, we proposed a local measure named the edge density coefficient, which could indicate whether an edge locates a dense subgraph or not. Simulation results showed that this measure could improve both the accuracy and speed in detecting dense subgraphs. Thus, the G-N algorithm can be extended to large biological networks by this local measure. Finally, we applied this algorithm to microarray data sets of Saccharomyces cerevisiae, and performed the gene ontology analysis of the result by the GOEAST.
  • loading
  • M. Girvan, M.E.J. Newman, “Community structure in social and biological networks”, Proc. Natl. Acad. Sci. USA, Vol.99, pp.7821-7826, 2002.
    F. Radicchi, C. Castellano, F. Cecconi et al., “Defining and identifying communities in networks”, PNAS, Vol.101, No.9, pp.2658-2663, 2004.
    M.E.J. Newman, M. Girvan, “Finding and evaluating community structure in networks”, Physical Review E, Vol.69, No.2, Article Number: 026113, 2004.
    M.E.J. Newman, “Fast algorithm for detecting community structure in networks”, Physical Review E, Vol.69, No.6, Article Number: 066133, 2004.
    M.E.J. Newman, “Modularity and community structure in networks”, PNAS, Vol.103, No.23, pp.8577-8582, 2006.
    J.W. Pinney, D.R. Westhead, “Betweenness-based decomposition methods for social and biological networks”, In Interdisciplinary Statistics and Bioinformatics, Leeds University Press,pp.87-90, 2007.
    J. Xiang, K. Hu, Y. Tang, “A class of improved algorithms for detecting communities in complex networks”, Physica A, Vol.387, No.13, pp.3327-3334, 2008.
    I. Shmulevich, E.R. Dougherty, “Genomic Signal Processing”, Princeton Series in Applied Mathematics, Princeton Univers inceton University Press, pp.277, 2007.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (297) PDF downloads(2176) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return