IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v20y2010i4d10.1007_s10878-009-9212-2.html
   My bibliography  Save this article

Separator-based data reduction for signed graph balancing

Author

Listed:
  • Falk Hüffner

    (Friedrich-Schiller-Universität Jena)

  • Nadja Betzler

    (Friedrich-Schiller-Universität Jena)

  • Rolf Niedermeier

    (Friedrich-Schiller-Universität Jena)

Abstract

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

Suggested Citation

  • Falk Hüffner & Nadja Betzler & Rolf Niedermeier, 2010. "Separator-based data reduction for signed graph balancing," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 335-360, November.
    • Handle: RePEc:spr:jcomop:v:20:y:2010:i:4:d:10.1007_s10878-009-9212-2
    DOI: 10.1007/s10878-009-9212-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9212-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-009-9212-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Boginski, Vladimir & Butenko, Sergiy & Pardalos, Panos M., 2005. "Statistical analysis of financial networks," Computational Statistics & Data Analysis, Elsevier, vol. 48(2), pages 431-443, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sajjad Salehi & Fattaneh Taghiyareh, 2020. "Stabilizing social structure via modifying local patterns," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 1079-1095, May.
    2. Rafael Esteves Mansano & Luiz Emilio Allem & Renata Raposo Del-Vecchio & Carlos Hoppen, 2022. "Balanced portfolio via signed graphs and spectral clustering in the Brazilian stock market," Quality & Quantity: International Journal of Methodology, Springer, vol. 56(4), pages 2325-2340, August.
    3. Mario Levorato & Rosa Figueiredo & Yuri Frota & Lúcia Drummond, 2017. "Evaluating balancing on social networks through the efficient solution of correlation clustering problems," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 467-498, December.
    4. Figueiredo, Rosa & Frota, Yuri, 2014. "The maximum balanced subgraph of a signed graph: Applications and solution approaches," European Journal of Operational Research, Elsevier, vol. 236(2), pages 473-487.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Teh, Boon Kin & Goo, Yik Wen & Lian, Tong Wei & Ong, Wei Guang & Choi, Wen Ting & Damodaran, Mridula & Cheong, Siew Ann, 2015. "The Chinese Correction of February 2007: How financial hierarchies change in a market crash," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 225-241.
    2. Stosic, Darko & Stosic, Dusan & Ludermir, Teresa B. & Stosic, Tatijana, 2018. "Collective behavior of cryptocurrency price changes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 499-509.
    3. Marton Gosztonyi, 2021. "A Snapshot of the Ownership Network of the Budapest Stock Exchange," Financial and Economic Review, Magyar Nemzeti Bank (Central Bank of Hungary), vol. 20(3), pages 31-58.
    4. Lillo, Felipe & Valdés, Rodrigo, 2016. "Dynamics of financial markets and transaction costs: A graph-based study," Research in International Business and Finance, Elsevier, vol. 38(C), pages 455-465.
    5. Xue Guo & Hu Zhang & Tianhai Tian, 2019. "Multi-Likelihood Methods for Developing Stock Relationship Networks Using Financial Big Data," Papers 1906.08088, arXiv.org.
    6. Wang, Gang-Jin & Chen, Yang-Yang & Si, Hui-Bin & Xie, Chi & Chevallier, Julien, 2021. "Multilayer information spillover networks analysis of China’s financial institutions based on variance decompositions," International Review of Economics & Finance, Elsevier, vol. 73(C), pages 325-347.
    7. Erick Treviño Aguilar, 2020. "The interdependency structure in the Mexican stock exchange: A network approach," PLOS ONE, Public Library of Science, vol. 15(10), pages 1-31, October.
    8. Elisa Letizia & Fabrizio Lillo, 2017. "Corporate payments networks and credit risk rating," Papers 1711.07677, arXiv.org, revised Sep 2018.
    9. Nie, Chun-Xiao, 2017. "Correlation dimension of financial market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 632-639.
    10. Zugang Liu, 2013. "The co-evolution of integrated corporate financial networks and supply chain networks with insolvency risk," Computational Management Science, Springer, vol. 10(2), pages 253-275, June.
    11. Frank Emmert-Streib & Matthias Dehmer, 2010. "Influence of the Time Scale on the Construction of Financial Networks," PLOS ONE, Public Library of Science, vol. 5(9), pages 1-9, September.
    12. Radhakrishnan, Srinivasan & Duvvuru, Arjun & Sultornsanee, Sivarit & Kamarthi, Sagar, 2016. "Phase synchronization based minimum spanning trees for analysis of financial time series with nonlinear correlations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 259-270.
    13. Seyed Soheil Hosseini & Nick Wormald & Tianhai Tian, 2019. "A Weight-based Information Filtration Algorithm for Stock-Correlation Networks," Papers 1904.06007, arXiv.org.
    14. Oleg Shirokikh & Grigory Pastukhov & Vladimir Boginski & Sergiy Butenko, 2013. "Computational study of the US stock market evolution: a rank correlation-based network model," Computational Management Science, Springer, vol. 10(2), pages 81-103, June.
    15. Nie, Chun-Xiao, 2022. "Analysis of critical events in the correlation dynamics of cryptocurrency market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 586(C).
    16. Xu, Shiyun & Shao, Menglin & Qiao, Wenxuan & Shang, Pengjian, 2018. "Generalized AIC method based on higher-order moments and entropy of financial time series," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 505(C), pages 1127-1138.
    17. François Caron & Emily B. Fox, 2017. "Sparse graphs using exchangeable random measures," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(5), pages 1295-1366, November.
    18. Biplab Bhattacharjee & Muhammad Shafi & Animesh Acharjee, 2017. "Investigating the Evolution of Linkage Dynamics among Equity Markets Using Network Models and Measures: The Case of Asian Equity Market Integration," Data, MDPI, vol. 2(4), pages 1-28, December.
    19. Nie, Chun-Xiao, 2023. "Time-varying characteristics of information flow networks in the Chinese market: An analysis based on sector indices," Finance Research Letters, Elsevier, vol. 54(C).
    20. Chun-Xiao Nie & Fu-Tie Song, 2021. "Entropy of Graphs in Financial Markets," Computational Economics, Springer;Society for Computational Economics, vol. 57(4), pages 1149-1166, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:20:y:2010:i:4:d:10.1007_s10878-009-9212-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.