Skip to main content
SpringerLink
Log in

Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs

  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

Abstract

The minimum feedback arc set problem asks to delete a minimum number of arcs (directed edges) from a digraph (directed graph) to make it free of any directed cycles. In this work we approach this fundamental cycle-constrained optimization problem by considering a generalized task of dividing the digraph into D layers of equal size. We solve the D-segmentation problem by the replica-symmetric mean field theory and belief-propagation heuristic algorithms. The minimum feedback arc density of a given random digraph ensemble is then obtained by extrapolating the theoretical results to the limit of large D. A divide-and-conquer algorithm (nested-BPR) is devised to solve the minimum feedback arc set problem with very good performance and high efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Lan, Y., Mezić, I.: On the architecture of cell regulation networks. BMC Syst. Biol. 5, 37 (2011)

    Article  Google Scholar 

  2. Gupte, M., Shankar, P., Li, J., Muthukrishnan, S., Iftode, L.: Finding hierarchy in directed online social networks. In: Proceedings of the twentieth International World Wide Web Conference, pp. 557–566 (Association for Computing Machinery, Hyderabad, India, 2011)

  3. Xu, J., Lan, Y.: Hierarchical feedback modules and reaction hubs in cell signaling networks. PLoS ONE 10(5), e0125886 (2015)

    Article  Google Scholar 

  4. Zhao, J.-H., Zhou, H.-J.: Feedback arcs and node hierarchy in directed networks. Chin. Phys. B 26, 078901 (2017)

  5. Ispolatove, I., Maslov, S.: Detection of the dominant direction of information flow and feedback links in densely interconnected regulatory networks. BMC Bioinform. 9, 424 (2008)

    Article  Google Scholar 

  6. Domínguez-García, V., Pigolotti, S., Muñoz, M.A.: Inherent directionality explains the lack of feedback loops in empirical networks. Sci. Rep. 4, 7497 (2014)

    Article  Google Scholar 

  7. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  8. Galinier, P., Lemamou, E., Bouzidi, M.W.: Applying local search to the feedback vertex set problem. J. Heuristics 19, 797–818 (2013)

    Article  Google Scholar 

  9. Fu, Y., Anderson, P.W.: Application of statistical mechanics to np-complete problems in combinatorial optimisation. J. Phys. A 19, 1605–1620 (1986)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  10. Mézard, M., Parisi, G.: Mean-field theory of randomly frustrated systems with finite connectivity. Europhys. Lett. 3, 1067–1074 (1987)

    Article  ADS  Google Scholar 

  11. Sherrington, D., Wong, K.Y.M.: Graph bipartitioning and the bethe spin glass. J. Phys. A 20, L785–L791 (1987)

    Article  ADS  MathSciNet  Google Scholar 

  12. Lai, P.-Y., Goldschidt, Y.Y.: Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph. J. Stat. Phys. 48, 513–529 (1987)

    Article  ADS  MathSciNet  Google Scholar 

  13. Šulc, P., Zdeborová, L.: Belief propagation for graph partitioning. J. Phys. A 43, 285003 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kawamoto, T., Kabashima, Y.: Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors. Phys. Rev. E 91, 062803 (2015)

    Article  ADS  MathSciNet  Google Scholar 

  15. Mézard, M., Parisi, G.: The bethe lattice spin glass revisited. Eur. Phys. J. B 20, 217–233 (2001)

    Article  ADS  MathSciNet  Google Scholar 

  16. Yedidia, J.S., Freeman, W.T., Weiss, Y.: Understanding belief propagation and its generalizations. Technical Reports Mitsubishi Electric Research Laboratories (2001)

  17. Yedidia, J.S., Freeman, W.T., Weiss, Y.: Constructing free-energy approximations and generalized belief-propagation algorithms. IEEE Trans. Inf. Theory 51, 2282–2312 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, New York (2009)

    Book  MATH  Google Scholar 

  19. Xiao, J.-Q., Zhou, H.J.: Partition function loop series for a general graphical model: free-energy corrections and message-passing equations. J. Phys. A 44, 425001 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Zhou, H.J., Wang, C.: Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results. J. Stat. Phys. 148, 513–547 (2012)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  21. Mori, R.: Loop calculus for non-binary alphabets using concepts from information genometry. IEEE Tran. Inf. Theory 61, 1887–1904 (2015)

    Article  MATH  Google Scholar 

  22. Zhou, H.-J.: Spin Glass and Message Passing. Science Press, Beijing (2015)

    Google Scholar 

  23. Zhou, H.-J.: Spin glass approach to the feedback vertex set problem. Eur. Phys. J. B 86, 455 (2013)

    Article  ADS  MathSciNet  Google Scholar 

  24. Bau, S., Wormald, N.C., Zhou, S.: Decycling numbers of random regular graphs. Random Struct. Algorithms 21, 397–413 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Haxell, P., Pikhurko, O., Thomason, A.: Maximum acyclic and fragmented sets in regular graphs. J. Graph Theory 57, 149–156 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812–815 (2002)

    Article  ADS  Google Scholar 

  27. Marino, R., Parisi, G., Ricci-Tersenghi, F.: The backtracking survey propagation algorithm for solving random \(k\)-sat problems. Nat. Commun. 7, 12996 (2016)

    Article  ADS  Google Scholar 

  28. Braunstein, A., Zecchina, R.: Learning by message passing in networks of discrete synapses. Phys. Rev. Lett. 96, 030201 (2006)

    Article  ADS  MathSciNet  Google Scholar 

  29. Zhou, H.-J.: A spin glass approach to the directed feedback vertex set problem. J. Stat. Mech. 2016, 12 (2016)

    Google Scholar 

  30. Bauke, H., Mertens, S.: Random numbers for large-scale distributed monte carlo simulations. Phys. Rev. E 75, 066701 (2007)

    Article  ADS  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank Dr. Jin-Hua Zhao for an earlier collaboration which stimulated the present Project, and thank Dr. Heiko Bauke for a helpful correspondence on the TRNG library of random number generators [30] which was called in our computer simulations. One of the authors (HJZ) acknowledges the hospitality of the Asia Pacific Center for Theoretical Physics (APCTP, Pohang, Korea) where the theoretical part of this Project was carried out during a short visit in November 2016. This research was partially supported by the National Natural Science Foundation of China (Grant Numbers 11121403 and 11647601).

Author information

Authors and Affiliations

  1. Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing, 100190, China

    Yi-Zhi Xu & Hai-Jun Zhou

  2. School of Physical Sciences, University of Chinese Academy of Sciences, Beijing, 100049, China

    Yi-Zhi Xu & Hai-Jun Zhou

Authors
  1. Yi-Zhi Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hai-Jun Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hai-Jun Zhou.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, YZ., Zhou, HJ. Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs. J Stat Phys 169, 187–202 (2017). https://doi.org/10.1007/s10955-017-1860-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10955-017-1860-5

Keywords

Search

Navigation