Abstract
Different fields of science use network representation as a framework to model their systems. The analysis of network structure can give us essential information about the system. However, the size of such a network can limit the applicability of some fundamental techniques like mathematical programming. Thus, here we propose a novel network size reduction technique based on a clique filtering approach. Our goal is twofold: (1) reduce the network size and speed up the community detection process, and (2) preserve the modularity of the original partition in the context of the exact model. Conducted experiments show the feasibility and correctness of the proposed technique.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, G., Kempe, D.: Modularity-maximizing graph communities via mathematical programming. Eur. Phys. J. B 66(3), 409–418 (2008)
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Modern Phys. 74(1), 47 (2002). https://doi.org/10.1103/RevModPhys.74.47
Arenas, A., Duch, J., Fernández, A., Gómez, S.: Size reduction of complex networks preserving modularity. New J. Phys. 9(6), 176 (2007). https://doi.org/10.1088/1367-2630/9/6/176
Bonchi, F., Morales, G.D.F., Gionis, A., Ukkonen, A.: Activity preserving graph simplification. Data Min. Knowl. Discov. 27(3), 321–343 (2013)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)
Fortunato, S., Hric, D.: Community detection in networks: a user guide. Phys. Rep. 659, 1–44 (2016)
Gemmetto, V., Cardillo, A., Garlaschelli, D.: Irreducible network backbones: unbiased graph filtering via maximum entropy. arXiv preprint arXiv:1706.00230 (2017)
Gionis, A., Rozenshtein, P., Tatti, N., Terzi, E.: Community-aware network sparsification. In: Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 426–434. SIAM (2017)
IBM: IBM ILOG CPLEX 12.7.1 (1987–2017)
Kim, J.R., Kim, J., Kwon, Y.K., Lee, H.Y., Heslop-Harrison, P., Cho, K.H.: Reduction of complex signaling networks to a representative kernel. Sci. Signal. 4(175), ra35–ra35 (2011)
Miyauchi, A., Sukegawa, N.: Redundant constraints in the standard formulation for the clique partitioning problem. Optim. Lett. 9(1), 199–207 (2015)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004). https://doi.org/10.1103/PhysRevE.69.026113
Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003). https://doi.org/10.1137/S003614450342480
Newman, M.E.: Analysis of weighted networks. Phys. Rev. E 70(5), 056131 (2004)
Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582 (2006). https://doi.org/10.1073/pnas.0601602103
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015). http://networkrepository.com
Stanley, N., Kwitt, R., Niethammer, M., Mucha, P.J.: Compressing networks with super nodes. CoRR abs/1706.04110 (2017). http://arxiv.org/abs/1706.04110
Strogatz, S.H.: Exploring complex networks. Nature 410(6825), 268–276 (2001). https://doi.org/10.1038/35065725
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998). https://doi.org/10.1038/30918
Xiao, Y., MacArthur, B.D., Wang, H., Xiong, M., Wang, W.: Network quotients: structural skeletons of complex systems. Phys. Rev. E 78(4), 046102 (2008)
Acknowledgment
M.G.Q. acknowledges the support by São Paulo Research Foundation (FAPESP, Proc. 2011/18496-7 & 2015/50122-0) and by the the Brazilian National Research Council (CNPq Proc. 310908/2015-9 & 434886/2018-1). L.A.N.L. acknowledges the support by (CNPq Proc. 301836/2014-0) and L.H.N.L. acknowledges the support by Coordination of Superior Level Staff Improvement (CAPES).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Lorena, L.H.N., Quiles, M.G., Lorena, L.A.N. (2019). Improving the Performance of an Integer Linear Programming Community Detection Algorithm Through Clique Filtering. In: Misra, S., et al. Computational Science and Its Applications – ICCSA 2019. ICCSA 2019. Lecture Notes in Computer Science(), vol 11619. Springer, Cham. https://doi.org/10.1007/978-3-030-24289-3_56
Download citation
DOI: https://doi.org/10.1007/978-3-030-24289-3_56
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24288-6
Online ISBN: 978-3-030-24289-3
eBook Packages: Computer ScienceComputer Science (R0)