IDEAS home Printed from
   My bibliography  Save this paper

The Analysis of Split Graphs in Social Networks Based on the K-Cardinality Assignment Problem


  • Belik, Ivan

    (Dept. of Business and Management Science, Norwegian School of Economics)


In terms of social networks, split graphs correspond to the variety of interpersonal and intergroup relations. In this paper we analyse the interaction between the cliques (socially strong and trusty groups) and the independent sets (fragmented and non-connected groups of people) as the basic components of any split graph. Based on the Semi-Lagrangean relaxation for the k-cardinality assignment problem, we show the way of minimizing the socially risky interactions between the cliques and the independent sets within the social network.

Suggested Citation

  • Belik, Ivan, 2014. "The Analysis of Split Graphs in Social Networks Based on the K-Cardinality Assignment Problem," Discussion Papers 2014/8, Norwegian School of Economics, Department of Business and Management Science.
  • Handle: RePEc:hhs:nhhfms:2014_008

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. R. Luce & Albert Perry, 1949. "A method of matrix analysis of group structure," Psychometrika, Springer;The Psychometric Society, vol. 14(2), pages 95-116, June.
    Full references (including those not matched with items on IDEAS)

    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. Noah E. Friedkin, 1984. "Structural Cohesion and Equivalence Explanations of Social Homogeneity," Sociological Methods & Research, , vol. 12(3), pages 235-261, February.
    2. Zhu, Yongjun & Yan, Erjia, 2017. "Examining academic ranking and inequality in library and information science through faculty hiring networks," Journal of Informetrics, Elsevier, vol. 11(2), pages 641-654.
    3. Etienne Farvaque & Frédéric Gannon, 2018. "Profiling giants: the networks and influence of Buchanan and Tullock," Public Choice, Springer, vol. 175(3), pages 277-302, June.
    4. Vanhaverbeke, W.P.M. & Beerkens, B.E. & Duysters, G.M., 2003. "Explorative and exploitative learning strategies in technology-based alliance networks," Working Papers 03.22, Eindhoven Center for Innovation Studies.
    5. K. Parthasarathy, 1964. "Enumeration of paths in digraphs," Psychometrika, Springer;The Psychometric Society, vol. 29(2), pages 153-165, June.
    6. Nasirian, Farzaneh & Mahdavi Pajouh, Foad & Balasundaram, Balabhaskar, 2020. "Detecting a most closeness-central clique in complex networks," European Journal of Operational Research, Elsevier, vol. 283(2), pages 461-475.
    7. William Ray Arney, 1973. "A Refined Status Index for Sociometric Data," Sociological Methods & Research, , vol. 1(3), pages 329-346, February.
    8. Lawrence Hubert, 1974. "Some applications of graph theory to clustering," Psychometrika, Springer;The Psychometric Society, vol. 39(3), pages 283-309, September.
    9. Chitra Balasubramaniam & Sergiy Butenko, 2017. "On robust clusters of minimum cardinality in networks," Annals of Operations Research, Springer, vol. 249(1), pages 17-37, February.
    10. Gouvêa, Alessandra M.M.M. & Rubido, Nicolás & Macau, Elbert E.N. & Quiles, Marcos G., 2022. "Importance of Numerical Implementation and Clustering Analysis in Force-Directed Algorithms for Accurate Community Detection," Applied Mathematics and Computation, Elsevier, vol. 431(C).
    11. Fetta, Angelico & Harper, Paul & Knight, Vincent & Williams, Janet, 2018. "Predicting adolescent social networks to stop smoking in secondary schools," European Journal of Operational Research, Elsevier, vol. 265(1), pages 263-276.
    12. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    13. Theodore Tsekeris, 2017. "Network analysis of inter-sectoral relationships and key sectors in the Greek economy," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 12(2), pages 413-435, July.
    14. Santella, Paolo & Drago, Carlo & Polo, Andrea, 2007. "The Italian Chamber of Lords Sits on Listed Company Boards: An Empirical Analysis of Italian Listed Company Boards from 1998 to 2006," MPRA Paper 2265, University Library of Munich, Germany.
    15. Verbeke, W.J.M.I. & Wuyts, S.H.K., 2006. "Moving in Social Circles – Social Circle Membership and Performance Implications," ERIM Report Series Research in Management ERS-2006-041-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    16. Idan Menashe & Pascal Grange & Eric C Larsen & Sharmila Banerjee-Basu & Partha P Mitra, 2013. "Co-expression Profiling of Autism Genes in the Mouse Brain," PLOS Computational Biology, Public Library of Science, vol. 9(7), pages 1-10, July.
    17. Nadine V. Kegen, 2015. "Cohesive subgroups in academic networks: unveiling clique integration of top-level female and male researchers," Scientometrics, Springer;Akadémiai Kiadó, vol. 103(3), pages 897-922, June.
    18. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    19. Ozman, Müge, 2003. "Self-Organizing Inter-Firm Networks," Research Memorandum 022, Maastricht University, Maastricht Economic Research Institute on Innovation and Technology (MERIT).
    20. Melisew Tefera Belachew & Nicolas Gillis, 2017. "Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation," Journal of Optimization Theory and Applications, Springer, vol. 173(1), pages 279-296, April.

    More about this item


    Social networks; split graphs; k-cardinality assignment;
    All these keywords.

    JEL classification:

    • C00 - Mathematical and Quantitative Methods - - General - - - General
    • C60 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - General
    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    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:hhs:nhhfms:2014_008. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: .

    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: Stein Fossen (email available below). General contact details of provider: .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.