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. 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.
    2. Sajjad Salehi & Fattaneh Taghiyareh, 2020. "Stabilizing social structure via modifying local patterns," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 1079-1095, May.
    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. D'Arcangelis, Anna Maria & Rotundo, Giulia, 2021. "Herding in mutual funds: A complex network approach," Journal of Business Research, Elsevier, vol. 129(C), pages 679-686.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Xue Guo & Hu Zhang & Tianhai Tian, 2019. "Multi-Likelihood Methods for Developing Stock Relationship Networks Using Financial Big Data," Papers 1906.08088, arXiv.org.
    7. 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.
    8. Neto, José de Paula Neves & Figueiredo, Daniel Ratton, 2023. "Ranking influential and influenced stocks over time using transfer entropy networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 630(C).
    9. Gang-Jin Wang & Chi Xie & Kaijian He & H. Eugene Stanley, 2017. "Extreme risk spillover network: application to financial institutions," Quantitative Finance, Taylor & Francis Journals, vol. 17(9), pages 1417-1433, September.
    10. Výrost, Tomáš & Lyócsa, Štefan & Baumöhl, Eduard, 2015. "Granger causality stock market networks: Temporal proximity and preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 427(C), pages 262-276.
    11. 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.
    12. Chu, Jeffrey & Zhang, Yuanyuan & Chan, Stephen & Nadarajah, Saralees, 2020. "Bias reduction in the population size estimation of large data sets," Computational Statistics & Data Analysis, Elsevier, vol. 145(C).
    13. Li, Jianxuan & Shi, Yingying & Cao, Guangxi, 2018. "Topology structure based on detrended cross-correlation coefficient of exchange rate network of the belt and road countries," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 509(C), pages 1140-1151.
    14. Elisa Letizia & Fabrizio Lillo, 2017. "Corporate payments networks and credit risk rating," Papers 1711.07677, arXiv.org, revised Sep 2018.
    15. Nie, Chun-Xiao, 2017. "Correlation dimension of financial market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 632-639.
    16. Yong Tang & Jason Jie Xiong & Zi-Yang Jia & Yi-Cheng Zhang, 2018. "Complexities in Financial Network Topological Dynamics: Modeling of Emerging and Developed Stock Markets," Complexity, Hindawi, vol. 2018, pages 1-31, November.
    17. 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.
    18. Anna Maria D’Arcangelis & Arianna Pierdomenico & Giulia Rotundo, 2024. "Impact of Brexit on STOXX Europe 600 Constituents: A Complex Network Analysis," Stats, MDPI, vol. 7(3), pages 1-20, June.
    19. 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.
    20. 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.

    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.