IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v584y2021ics0378437121006439.html
   My bibliography  Save this article

Community detection in directed acyclic graphs of adversary interactions

Author

Listed:
  • Wu, Ke
  • Liu, Xueming

Abstract

Certain real networks are represented as directed acyclic graphs (DAGs) and the links represent adversary interactions between two entities, such as food webs where links exist only from prey to predators and temporal war networks where links point from attackers to defenders. In such DAGs, similar nodes may form communities, such as top carnivores in food webs and war alliances in war networks, where nodes cannot be directly connected but have similar orders and neighbors. However, most previous community detection methods are developed based on an assumption that a link between nodes indicates similarity, not applicable to such cases. In this work, we define the community in DAGs of adversary interactions based on the nodes’ orders and similarities, and propose a Katz–Simrank method to detect communities. We first convert the DAG into an equivalent weighted undirected network based on nodes’ orders and similarities, then the problem of community detection in such DAG can be converted into an equivalent problem of detecting cliques in this weighted undirected network. We apply this method to both synthetic and real DAGs, such as food webs and war networks, and find that Katz–Simrank method could effectively identify communities and demonstrates superior performance over other baseline methods in DAG community detection.

Suggested Citation

  • Wu, Ke & Liu, Xueming, 2021. "Community detection in directed acyclic graphs of adversary interactions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 584(C).
  • Handle: RePEc:eee:phsmap:v:584:y:2021:i:c:s0378437121006439
    DOI: 10.1016/j.physa.2021.126370
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437121006439
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    File URL: https://libkey.io/10.1016/j.physa.2021.126370?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. Michael D. König & Dominic Rohner & Mathias Thoenig & Fabrizio Zilibotti, 2017. "Networks in Conflict: Theory and Evidence From the Great War of Africa," Econometrica, Econometric Society, vol. 85, pages 1093-1132, July.
    2. Leo Speidel & Taro Takaguchi & Naoki Masuda, 2015. "Community detection in directed acyclic graphs," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 88(8), pages 1-10, August.
    3. Chen, P. & Redner, S., 2010. "Community structure of the physical review citation network," Journal of Informetrics, Elsevier, vol. 4(3), pages 278-290.
    4. David Liben‐Nowell & Jon Kleinberg, 2007. "The link‐prediction problem for social networks," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 58(7), pages 1019-1031, May.
    5. Xueming Liu & Enrico Maiorino & Arda Halu & Kimberly Glass & Rashmi B. Prasad & Joseph Loscalzo & Jianxi Gao & Amitabh Sharma, 2020. "Robustness and lethality in multilayer biological molecular networks," Nature Communications, Nature, vol. 11(1), pages 1-12, December.
    6. Nima Dehmamy & Soodabeh Milanlouei & Albert-László Barabási, 2018. "A structural transition in physical networks," Nature, Nature, vol. 563(7733), pages 676-680, November.
    7. Martin Rosvall & Carl T Bergstrom, 2010. "Mapping Change in Large Networks," PLOS ONE, Public Library of Science, vol. 5(1), pages 1-7, January.
    8. Nima Dehmamy & Sergey V. Buldyrev & Shlomo Havlin & H. Eugene Stanley & Irena Vodenska, 2014. "Classical mechanics of economic networks," Papers 1410.0104, arXiv.org, revised Dec 2014.
    9. E. A. Leicht & G. Clarkson & K. Shedden & M. E.J. Newman, 2007. "Large-scale structure of time evolving citation networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 59(1), pages 75-83, September.
    10. Du, Ruijin & Wang, Ya & Dong, Gaogao & Tian, Lixin & Liu, Yixiao & Wang, Minggang & Fang, Guochang, 2017. "A complex network perspective on interrelations and evolution features of international oil trade, 2002–2013," Applied Energy, Elsevier, vol. 196(C), pages 142-151.
    11. 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.
    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. Greg Morrison & L Mahadevan, 2012. "Discovering Communities through Friendship," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-9, July.
    2. Lovro Šubelj & Nees Jan van Eck & Ludo Waltman, 2016. "Clustering Scientific Publications Based on Citation Relations: A Systematic Comparison of Different Methods," PLOS ONE, Public Library of Science, vol. 11(4), pages 1-23, April.
    3. Wenyuan Liu & Andrea Nanetti & Siew Ann Cheong, 2017. "Knowledge evolution in physics research: An analysis of bibliographic coupling networks," PLOS ONE, Public Library of Science, vol. 12(9), pages 1-19, September.
    4. Xiaoguang Wang & Qikai Cheng & Wei Lu, 2014. "Analyzing evolution of research topics with NEViewer: a new method based on dynamic co-word networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 101(2), pages 1253-1271, November.
    5. Cobo, M.J. & López-Herrera, A.G. & Herrera-Viedma, E. & Herrera, F., 2011. "An approach for detecting, quantifying, and visualizing the evolution of a research field: A practical application to the Fuzzy Sets Theory field," Journal of Informetrics, Elsevier, vol. 5(1), pages 146-166.
    6. Carissimo, Annamaria & Cutillo, Luisa & Feis, Italia De, 2018. "Validation of community robustness," Computational Statistics & Data Analysis, Elsevier, vol. 120(C), pages 1-24.
    7. Zhao, Star X. & Rousseau, Ronald & Ye, Fred Y., 2011. "h-Degree as a basic measure in weighted networks," Journal of Informetrics, Elsevier, vol. 5(4), pages 668-677.
    8. Wu, Jianshe & Zhang, Long & Li, Yong & Jiao, Yang, 2016. "Partition signed social networks via clustering dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 568-582.
    9. Jeong, Yujin & Park, Inchae & Yoon, Byungun, 2019. "Identifying emerging Research and Business Development (R&BD) areas based on topic modeling and visualization with intellectual property right data," Technological Forecasting and Social Change, Elsevier, vol. 146(C), pages 655-672.
    10. Wang, Wenya & Li, Zhenfu & Cheng, Xin, 2019. "Evolution of the global coal trade network: A complex network analysis," Resources Policy, Elsevier, vol. 62(C), pages 496-506.
    11. David Rezza Baqaee & Emmanuel Farhi, 2019. "The Macroeconomic Impact of Microeconomic Shocks: Beyond Hulten's Theorem," Econometrica, Econometric Society, vol. 87(4), pages 1155-1203, July.
    12. Gregory, Steve, 2012. "Ordered community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2752-2763.
    13. Ke Hu & Ju Xiang & Yun-Xia Yu & Liang Tang & Qin Xiang & Jian-Ming Li & Yong-Hong Tang & Yong-Jun Chen & Yan Zhang, 2020. "Significance-based multi-scale method for network community detection and its application in disease-gene prediction," PLOS ONE, Public Library of Science, vol. 15(3), pages 1-24, March.
    14. Yifei Zhou & Shaoyong Li & Yaping Liu, 2020. "Graph-based Method for App Usage Prediction with Attributed Heterogeneous Network Embedding," Future Internet, MDPI, vol. 12(3), pages 1-16, March.
    15. Cemal Eren Arbatlı & Quamrul H. Ashraf & Oded Galor & Marc Klemp, 2020. "Diversity and Conflict," Econometrica, Econometric Society, vol. 88(2), pages 727-797, March.
    16. Shiji Chen & Clément Arsenault & Yves Gingras & Vincent Larivière, 2015. "Exploring the interdisciplinary evolution of a discipline: the case of Biochemistry and Molecular Biology," Scientometrics, Springer;Akadémiai Kiadó, vol. 102(2), pages 1307-1323, February.
    17. Karimi, Fatemeh & Lotfi, Shahriar & Izadkhah, Habib, 2021. "Community-guided link prediction in multiplex networks," Journal of Informetrics, Elsevier, vol. 15(4).
    18. Cai, Ya-Jun & Lo, Chris K.Y., 2020. "Omni-channel management in the new retailing era: A systematic review and future research agenda," International Journal of Production Economics, Elsevier, vol. 229(C).
    19. Xiang, Ju & Tang, Yan-Ni & Gao, Yuan-Yuan & Zhang, Yan & Deng, Ke & Xu, Xiao-Ke & Hu, Ke, 2015. "Multi-resolution community detection based on generalized self-loop rescaling strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 432(C), pages 127-139.
    20. Marco Manacorda & Andrea Tesei, 2020. "Liberation Technology: Mobile Phones and Political Mobilization in Africa," Econometrica, Econometric Society, vol. 88(2), pages 533-567, March.

    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:eee:phsmap:v:584:y:2021:i:c:s0378437121006439. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.