Abstract
We give an account of an approach to community-structure detection in networks using linear programming: given a finite simple graph G, we assign penalties for manipulating this graph by either deleting or adding edges, and then consider the problem of turning G, by performing these two operations, at minimal total cost into a graph that represents a community structure, i.e., that is a disjoint union of complete subgraphs. We show that this minimization problem can be reformulated (and solved!) in terms of a one-parameter family of linear-programming problems relative to which some kind of a “second-order phase transition” can be observed, and we demonstrate by example that this interpretation provides a viable alternative for dealing with the much studied task of detecting community structures in networks. And by reporting our discussions with a leading ecologist, we demonstrate how our approach can be used to analyse food webs and to support the elucidation of their “global” implications.
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
Notes
- 1.
That is, the LP problem for which all requirements regarding the “integrality” of the solution vector have been dropped and only the requirement \( \chi_{T} (uv) \in [0,1] \) is kept.
References
Albert, R., Jeong, H., Barabási, A.-L.: Diameter of the World-Wide Web. Nature 401, 130–131 (1999)
Amaral, L.A.N., Scala, A., Barthélémy, M., Stanley, H.E.: Classes of samll-world networks. Proc. Natl. Acad. Sci. U.S.A. 97, 11149–11152 (2000)
Bagrow, J.P., Bollt, E.M.: Local method for detecting communities. Phys. Rev. E 72, 046108 (2005)
Baird, D., Ulanowicz, R.E.: The seasonal dynamics of the Chesapeake Bay ecosystem. Ecol. Monogr. 59, 329–364 (1989)
Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Chen, W.Y.C., Dress, A.W.M., Yu,W.Q.: Community structures of networks. In: IET Systems Biology, Proceedings Mathematics Aspects of Computer and Information Sciences (MACIS 2006), Beijing, China, and Mathematics computer science vol. 1, pp. 441–457 (2008)
Chen, W.Y.C., Dress, A.W.M., Yu,W.Q.: Checking the reliability of a linear-programming based approach towards detecting community structures in networks, Proceedings International Conference on Computational Systems Biology (ICCSB 2006), Shanghai, China, and IET System Biology, vol. 5, pp. 286–291 (2007)
Clauset. A., Newman M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E. 69, 026113 (2004)
Clauset. A.: Finding local community structure in networks. Phys. Rev. E. 72, 026132 (2005)
Davidson, E., et al.: A genomic regulatory network for development. Science 295, 1669–1678 (2002)
Flake, G.W., Lawrence, S.R., Giles, C.L., Coetzee, F.M.: Self-organization and identification of web communities. IEEE Comput. 35, 66–71 (2002)
Fortunao, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010). doi:10.1016/j.physrep.2009.11.002
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)
Grötschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45, 59–96 (1989)
Grötschel, M., Wakabayashi, Y.: Facets of the clique partitioning polytope. Math. Program. 47, 367–387 (1990)
Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabási, A.-L.: The large-scale organization of metabolic networks. Nature 407, 651–654 (2000)
Jeong, H., Mason, S.P., Barabási, A.-L., Oltvai, Z.N.: Lethality and centrality in protein networks. Nature 411, 41–42 (2001)
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291–307 (1970)
Kleinberg, J., Lawrence, S.: The structure of the Web. Science 294, 1849–1850 (2001)
Newman, M.E.: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. U.S.A. 98, 404–409 (2001)
Newman, M.E.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)
Pocklington, A., Cumiskey, M., Armstrong, J., Grant, S.: The proteomes of neurotransmitter receptor complexes form modular networks with distributed functionality underlying plasticity and behaviour. Mol. Syst. Biol. (2006). doi: 10.1038/msb4100041
Porter, M.A., Onnela, J.-P., Mucha, P.J.: Communities in networks. Not. Amer. Math. Soc. 56(9), 1082–1097, 1164–1166 (2009)
Pothen, A., Simon, H., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 430–452 (1990)
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and idetifying communities in networks. Proc. Natl. Acad. Sci. U.S.A. 101, 2658–2663 (2004)
Redner, S.: How popular is your paper? an empirical study of the citation distribution. Eur. Phys. J. B 4, 131–134 (1998)
Reichardt, J., Bornholdt, S.: Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett. 93, 218701 (2004)
Scott, J.: Social Network Analysis: A Handbook., 2nd edn. Sage, London, (2000)
Strogatz, S.H.: Exploring complex networks. Nature 410, 268–276 (2001)
Tyler, J.R., Wilkinson, D.M., Huberman, B.A.: Email as spectroscopy: automated discovery of community structure within organizations. In: Huysman, M., Wenger, E., Wulf. V. (eds.) Proceedings of the first international conference on communities and technologies, Kluwer, Dordrecht (2003)
Wasserman, S., Faust, K.: Social Network Analysis. Cambridge University Press, Cambridge (1994)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small world’ networks. Nature 393, 440–442 (1998)
Watts, D.J.: Small Worlds. Princeton University Press, Princeton (1999)
Williams, R.J., Martinez, N.D.: Simple rules yield complex food webs. Nature 404, 180–183 (2000)
Wu, F., Huberman, B.A.: Finding communities in linear time: a physics approach. Eur. Phys. J. B 38, 331–338 (2004)
Zachary, W.W.: An information flow model for conflict and fisson in small groups. J. Anthropol. Res. 33, 452–473 (1977)
Acknowledgments
The authors are grateful to R.Ulanowicz and C. Bondavalli for their expert comments on our results and many helpful suggestions, and to M. Briesemann for his help on the data packing.
This work was financially supported by the Max Planck Society of Germany, the 973 Project on Mathematical Mechanization, the Ministry of Education, the Ministry of Science and Technology, and the National Science Foundation of China.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Chen, W.Y.C., Dress, A., Yu, W.Q. (2014). Detecting Community Structures in Networks Using a Linear-Programming Based Approach: a Review. In: Pedrycz, W., Chen, SM. (eds) Social Networks: A Framework of Computational Intelligence. Studies in Computational Intelligence, vol 526. Springer, Cham. https://doi.org/10.1007/978-3-319-02993-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-02993-1_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02992-4
Online ISBN: 978-3-319-02993-1
eBook Packages: EngineeringEngineering (R0)