Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient

GUAN Bo; ZAN Xiangzhen; XIAO Biyu; MA Runnian; ZHANG Fengyue; LIU Wenbin

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(3): 517-520

GUAN Bo, ZAN Xiangzhen, XIAO Biyu, et al., “Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 517-520, 2013,

Citation:

GUAN Bo, ZAN Xiangzhen, XIAO Biyu, et al., “Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 517-520, 2013,

GUAN Bo, ZAN Xiangzhen, XIAO Biyu, et al., “Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 517-520, 2013,

Citation:

PDF( 388 KB)

Detecting Dense Subgraphs in Complex Networks Based on Edge Density Coefficient

1.
College of Electron and Information Engineering, Ningbo University of Technology, Ningbo, Zhejiang 315016, China;
2.
Department of Physics and Electronic Information Engineering, Wenzhou University, Wenzhou, Zhejiang 325035, China;
3.
Telecommunication Institute, Air Force Engineering University, Xi'an 710077, China;
4.
Department of Biomedical Engineering, School of Life Science and Technology, Beijing Institute of Technology, Beijing 100081, China

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

Abstract

Abstract

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.
- Complex network,
- Dense subgraph,
- Microarray data

FullText(HTML)

References(8)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views