Deep Auto-encoded Clustering Algorithm for Community Detection in Complex Networks

WANG Feifan; ZHANG Baihai; CHAI Senchun

doi:10.1049/cje.2019.03.019

Volume 28 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2019 > 28(3): 489-496

WANG Feifan, ZHANG Baihai, CHAI Senchun, “Deep Auto-encoded Clustering Algorithm for Community Detection in Complex Networks,” Chinese Journal of Electronics, vol. 28, no. 3, pp. 489-496, 2019, doi: 10.1049/cje.2019.03.019

Citation:

WANG Feifan, ZHANG Baihai, CHAI Senchun, “Deep Auto-encoded Clustering Algorithm for Community Detection in Complex Networks,” Chinese Journal of Electronics, vol. 28, no. 3, pp. 489-496, 2019, doi: 10.1049/cje.2019.03.019

Citation:

PDF( 1093 KB)

Deep Auto-encoded Clustering Algorithm for Community Detection in Complex Networks

doi: 10.1049/cje.2019.03.019

School of Automation, Beijing Institute of Technology, Beijing 100081, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61573061).

Received Date: 2018-01-31
Publish Date: 2019-05-10

Abstract

Abstract

The prevalence of deep learning has inspired innovations in numerous research fields including community detection, a cornerstone in the advancement of complex networks. We propose a novel community detection algorithm called the Deep auto-encoded clustering algorithm (DAC), in which unsupervised and sparse single autoencoders are trained and piled up one after another to embed key community information in a lowerdimensional representation, such that it can be handled easier by clustering strategies. Extensive comparison tests undertaken on synthetic and real world networks reveal two advantages of the proposed algorithm: on the one hand, DAC shows higher precision than thek-means community detection method benefiting from the integration of sparsity constraints. On the other hand, DAC runs much faster than the spectral community detection algorithm based on the circumvention of the time-consuming eigenvalue decomposition procedure.
- Deep learning,
- Community detection,
- Autoencoder,
- Complex networks

FullText(HTML)

References(28)

References

M.E.J. Newman, Networks:An Introduction, Oxford University Press, London, UK, pp.21-97, 2010.

Y. Zheng, D. Zhang and K. Xie, "A geography-intimacy-based algorithm for data forwarding in mobile social networks", Chinese Journal of Electronics, Vol.25, No.5, pp.936-942, 2016.

M.E.J. Newman, "Community detection in networks:Modularity optimization and maximum likelihood are equivalent", Physical Review E, Vol.94, p.052315, 2016.

H.C. Tao, Y.Q. Wang, Z.A. Wu, et al., "Discovering overlapping communities by clustering local link structures", Chinese Journal of Electronics, Vol.26, No.2, pp.430-434, 2017.

S. Fortunato and D. Hric, "Community detection in networks:A user guide", Physics Reports, Vol.659, pp.1-44, 2016.

M. Girvan and M.E.J. Newman, "Community structure in social and biological networks", Proc. Natl. Acad. Sci. U.S.A., Vol.99, No.12, pp.7821-7826, 2002.

M.E.J. Newman and M. Girvan, "Finding and evaluating community structure in networks", Physical Review E, Vol.69, p.026113, 2004.

M.E.J. Newman, "A measure of betweenness centrality based on random walks", Social Networks, Vol.27, No.1, pp.39-54, 2005.

U. Brandes, D. Delling, M. Gaertler, et al., "On finding graph clusterings with maximum modularity", International Workshop on Graph-Theoretic Concepts in Computer Science, Dornburg, Germany, pp.121-132, 2007.

S. Li, Y. Chen, H. Du, et al., "A genetic algorithm with local search strategy for improved detection of community structure", Complexity, Vol.15, No.4, pp.53-60, 2010.

X. Zhang and M.E.J. Newman, "Multiway spectral community detection in networks", Physical Review E, Vol.92, p.052808, 2015.

M.E.J. Newman, "Spectral methods for community detection and graph partitioning", Physical Review E, Vol.88, p.042822, 2013.

A.Y. Ng, M.I. Jordan and Y. Weiss, "On spectral clustering:analysis and an algorithm", International Conference on Neural Information Processing Systems:Natural and Synthetic, Vancouver, British Columbia, Canada, pp.849-856, 2001.

D. Silver, J. Schrittwieser, K. Simonyan, et al., "Mastering the game of go without human knowledge", Nature, Vol.550, No.7676, pp.354-371, 2017.

S.G. Zhu, J.P. Du and N. Ren, "A novel simple visual tracking algorithm based on hashing and deep learning", Chinese Journal of Electronics, Vol.26, No.5, pp.1073-1078, 2017.

L.C. Yuan, "A new word clustering algorithm based on word similarity", Chinese Journal of Electronics, Vol.26, No.6, pp.1221-1226, 2017.

P.S. Huang, M. Kim, M.H. Johnson, et al, "Deep learning for monaural speech separation", IEEE International Conference on Acoustics, Speech and Signal Processing, Florence, Italy, pp.1562-1566, 2014.

G. Hinton and R. Satakhutdinov, "Reducing the dimensionality of data with neural networks", Science, Vol.313, No.5786, pp.504-7, 2006.

X.S. Wang, Y. Kong and Y.H. Cheng, "Dimensionality reduction for hyperspectral data based on sample-dependent repulsion graph regularized auto-encoder", Chinese Journal of Electronics, Vol.26, No.6, pp.1233-1238, 2017.

F. Tian, B. Gao, Q. Cui, et al., "Learning deep representations for graph clustering", Twenty-Eighth AAAI Conference on Artificial Intelligence, Quebéc City, Quebéc, Canada, pp.1293-1299, 2014.

J. Yang, D. Parikh and D. Batra, "Joint unsupervised learning of deep representations and image clusters", IEEE Conference on Computer Vision and Pattern Recognition, Los Alamitos, CA, USA, pp.5147-5156, 2016.

B. Yang, X. Fu, N.D. Sidiropoulos, et al., "Towards k-meansfriendly spaces:simultaneous deep learning and clustering", International Conference on Machine Learning, Sydney, Australia, pp.3861-3870, 2017.

T.V. Erven and P. Harremos, "Rényi divergence and Kullback-Leibler divergence", IEEE Transactions on Information Theory, Vol.60, No.7, pp.3797-3820, 2012.

P. Vincent, H. Larochelle, I. Lajoie, et al., "Stacked denoising autoencoders:Learning useful representations in a deep network with a local denoising criterion", Journal of Machine Learning Research, Vol.11, No.12, pp.3371-3408, 2010.

L. Li, K. Fan, Z. Zhang, et al., "Community detection algorithm based on local expansion k-means", Neural Networks, Vol.26, No.6, pp.589-605, 2016.

L. Danon, A. Díazguilera, J. Duch, et al., "Comparing community structure identification", J. Stat. Mech., Vol.9, p.09008, 2005.

W.W. Zachary, "An information flow model for conflict and fission in small groups", Journal of Anthropological Research, Vol.33, No.4, pp.452-473, 1977.

M.E.J. Newman, "Modularity and community structure in networks", Proc. Natl. Acad. Sci. U.S.A., Vol.103, No.23, pp.8577-8582, 2006.

Relative Articles

Supplements(0)

Cited By

Proportional views