IDEAS home Printed from https://ideas.repec.org/a/wsi/ijitdm/v16y2017i05ns021962201450028x.html
   My bibliography  Save this article

A New Method for Extracting the Hierarchical Organization of Networks

Author

Listed:
  • Weihua Zhan

    (College of Information Science and Engineering, Ningbo University, Ningbo 315211, China†Department of Computer Science and Technology, Tongji University, Shanghai 201804, China)

  • Jihong Guan

    (#x2020;Department of Computer Science and Technology, Tongji University, Shanghai 201804, China)

  • Zhongzhi Zhang

    (#x2021;School of Computer Science and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China)

Abstract

Extracting the hierarchical organization of networks is currently a pressing task for understanding complex networked systems. The hierarchy of a network is essentially defined by the heterogeneity of link densities of communities at different scales. Here, we define a top-level partition (TLP) as a bipartition of the network (or a sub-network) such that no top-level community (TLC) runs across the two parts. It has been found that a TLP generally has a higher modularity than a non-top-level (TLP) partition when their TLCs have similar sizes and when the link densities of neighboring levels are well separated from each other. A spectral TLP procedure is proposed here to search for TLPs of a network (or sub-network). To extract the hierarchical organization of large complex networks, an algorithm called TLPA has been developed based on the TLP. Experiments have shown that the method developed in this research extract hierarchy accurately from network data.

Suggested Citation

  • Weihua Zhan & Jihong Guan & Zhongzhi Zhang, 2017. "A New Method for Extracting the Hierarchical Organization of Networks," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 16(05), pages 1359-1385, September.
    • Handle: RePEc:wsi:ijitdm:v:16:y:2017:i:05:n:s021962201450028x
    DOI: 10.1142/S021962201450028X
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S021962201450028X
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S021962201450028X?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. Gergely Palla & Imre Derényi & Illés Farkas & Tamás Vicsek, 2005. "Uncovering the overlapping community structure of complex networks in nature and society," Nature, Nature, vol. 435(7043), pages 814-818, June.
    2. Dorogovtsev, S.N. & Mendes, J.F.F., 2003. "Evolution of Networks: From Biological Nets to the Internet and WWW," OUP Catalogue, Oxford University Press, number 9780198515906.
    3. J. M. Kumpula & J. Saramäki & K. Kaski & J. Kertész, 2007. "Limited resolution in complex network community detection with Potts model approach," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 56(1), pages 41-45, March.
    4. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    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. Dranev, Yakov & Kuznetsov, Boris & Kuzyk, Mikhail & Pogrebnyak, Evgeny & Simachev, Yuri, "undated". "Experience in Implementing Industrial Policy in the Russian Federation in 2000-2012: Institutional Features, Interest Groups, Main Lessons," Published Papers nvg137, Russian Presidential Academy of National Economy and Public Administration.

    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. Roth, Camille, 2007. "Empiricism for descriptive social network models," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(1), pages 53-58.
    2. Amulyashree Sridhar & Sharvani GS & AH Manjunatha Reddy & Biplab Bhattacharjee & Kalyan Nagaraj, 2019. "The Eminence of Co-Expressed Ties in Schizophrenia Network Communities," Data, MDPI, vol. 4(4), pages 1-23, November.
    3. Selen Onel & Abe Zeid & Sagar Kamarthi, 2011. "The structure and analysis of nanotechnology co-author and citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(1), pages 119-138, October.
    4. Liu, Xu & Forrest, Jeffrey Yi-Lin & Luo, Qiang & Yi, Dong-Yun, 2012. "Detecting community structure using biased random merging," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1797-1810.
    5. Pollner, Péter & Palla, Gergely & Vicsek, Tamás, 2010. "Clustering of tag-induced subgraphs in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(24), pages 5887-5894.
    6. Akshat Singhal & Song Cao & Christopher Churas & Dexter Pratt & Santo Fortunato & Fan Zheng & Trey Ideker, 2020. "Multiscale community detection in Cytoscape," PLOS Computational Biology, Public Library of Science, vol. 16(10), pages 1-10, October.
    7. Shen, Huawei & Cheng, Xueqi & Cai, Kai & Hu, Mao-Bin, 2009. "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(8), pages 1706-1712.
    8. Abdolhosseini-Qomi, Amir Mahdi & Yazdani, Naser & Asadpour, Masoud, 2020. "Overlapping communities and the prediction of missing links in multiplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 554(C).
    9. Rafael Rentería-Ramos & Rafael Hurtado-Heredia & B Piedad Urdinola, 2019. "Morbi-Mortality of the Victims of Internal Conflict and Poor Population in the Risaralda Province, Colombia," IJERPH, MDPI, vol. 16(9), pages 1-18, May.
    10. Chungmok Lee & Minh Pham & Myong K. Jeong & Dohyun Kim & Dennis K. J. Lin & Wanpracha Art Chavalitwongse, 2015. "A Network Structural Approach to the Link Prediction Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 249-267, May.
    11. Liu, Ji & Deng, Guishi, 2009. "Link prediction in a user–object network based on time-weighted resource allocation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(17), pages 3643-3650.
    12. Deijfen, M. & Kets, W., 2007. "Random Intersection Graphs with Tunable Degree Distribution and Clustering," Other publications TiSEM eddee3bd-5845-4b18-8734-b, Tilburg University, School of Economics and Management.
    13. Kininmonth, Stuart & van Oppen, Madeleine J.H. & Possingham, Hugh P., 2010. "Determining the community structure of the coral Seriatopora hystrix from hydrodynamic and genetic networks," Ecological Modelling, Elsevier, vol. 221(24), pages 2870-2880.
    14. Elisa Letizia & Paolo Barucca & Fabrizio Lillo, 2018. "Resolution of ranking hierarchies in directed networks," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-25, February.
    15. Ding, Jin & Lu, Yong-Zai & Chu, Jian, 2013. "Studies on controllability of directed networks with extremal optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(24), pages 6603-6615.
    16. Qiming Lu & G. Korniss & Boleslaw Szymanski, 2009. "The Naming Game in social networks: community formation and consensus engineering," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 4(2), pages 221-235, November.
    17. Deijfen, M. & Kets, W., 2007. "Random Intersection Graphs with Tunable Degree Distribution and Clustering," Discussion Paper 2007-008, Tilburg University, Center for Economic Research.
    18. Ma, Xiaoke & Wang, Bingbo & Yu, Liang, 2018. "Semi-supervised spectral algorithms for community detection in complex networks based on equivalence of clustering methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 786-802.
    19. Andrea Lancichinetti & Filippo Radicchi & José J Ramasco & Santo Fortunato, 2011. "Finding Statistically Significant Communities in Networks," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-18, April.
    20. Eustace, Justine & Wang, Xingyuan & Cui, Yaozu, 2015. "Community detection using local neighborhood in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 665-677.

    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:wsi:ijitdm:v:16:y:2017:i:05:n:s021962201450028x. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/ijitdm/ijitdm.shtml .

    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.