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

Exploring anti-community structure in networks with application to incompatibility of traditional Chinese medicine

Author

Listed:
  • Zhu, Jiajing
  • Liu, Yongguo
  • Zhang, Yun
  • Liu, Xiaofeng
  • Xiao, Yonghua
  • Wang, Shidong
  • Wu, Xindong

Abstract

Community structure is one of the most important properties in networks, in which a node shares its most connections with the others in the same community. On the contrary, the anti-community structure means the nodes in the same group have few or no connections with each other. In Traditional Chinese Medicine (TCM), the incompatibility problem of herbs is a challenge to the clinical medication safety. In this paper, we propose a new anti-community detection algorithm, Random non-nEighboring nOde expansioN (REON), to find anti-communities in networks, in which a new evaluation criterion, anti-modularity, is designed to measure the quality of the obtained anti-community structure. In order to establish anti-communities in REON, we expand the node set by non-neighboring node expansion and regard the node set with the highest anti-modularity as an anti-community. Inspired by the phenomenon that the node with higher degree has greater contribution to the anti-modularity, an improved algorithm called REONI is developed by expanding node set by the non-neighboring node with the maximum degree, which greatly enhances the efficiency of REON. Experiments on synthetic and real-world networks demonstrate the superiority of the proposed algorithms over the existing methods. In addition, by applying REONI to the herb network, we find that it can discover incompatible herb combinations.

Suggested Citation

  • Zhu, Jiajing & Liu, Yongguo & Zhang, Yun & Liu, Xiaofeng & Xiao, Yonghua & Wang, Shidong & Wu, Xindong, 2017. "Exploring anti-community structure in networks with application to incompatibility of traditional Chinese medicine," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 31-43.
  • Handle: RePEc:eee:phsmap:v:486:y:2017:i:c:p:31-43
    DOI: 10.1016/j.physa.2017.04.175
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437117304855
    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.2017.04.175?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. 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.
    2. Xiang, Ju & Hu, Tao & Zhang, Yan & Hu, Ke & Li, Jian-Ming & Xu, Xiao-Ke & Liu, Cui-Cui & Chen, Shi, 2016. "Local modularity for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 451-459.
    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. 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.
    2. 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.
    3. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    4. Lu Wei & Na Liu & Junhua Chen & Jihong Sun, 2022. "Topic Evolution of Chinese COVID-19 Policies Based on Co-Occurrence Clustering Network Analysis," Sustainability, MDPI, vol. 14(4), pages 1-21, February.
    5. Tasgin, Mursel & Bingol, Haluk O., 2018. "Community detection using preference networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 495(C), pages 126-136.
    6. Nan, Dong-Yang & Yu, Wei & Liu, Xiao & Zhang, Yun-Peng & Dai, Wei-Di, 2018. "A framework of community detection based on individual labels in attribute networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 523-536.
    7. Wang, Tao & Wang, Hongjue & Wang, Xiaoxia, 2015. "A novel cosine distance for detecting communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 437(C), pages 21-35.
    8. Wang, Tao & Chen, Shanshan & Wang, Xiaoxia & Wang, Jinfang, 2020. "Label propagation algorithm based on node importance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 551(C).
    9. Wang, Benyu & Gu, Yijun & Zheng, Diwen, 2022. "Community detection in error-prone environments based on particle cooperation and competition with distance dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    10. Chen, Xiangtao & Li, Juan, 2019. "Community detection in complex networks using edge-deleting with restrictions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 519(C), pages 181-194.
    11. Yang, Jin-Xuan & Zhang, Xiao-Dong, 2017. "Finding overlapping communities using seed set," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 467(C), pages 96-106.
    12. He, Chaobo & Tang, Yong & Liu, Hai & Fei, Xiang & Li, Hanchao & Liu, Shuangyin, 2019. "A robust multi-view clustering method for community detection combining link and content information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 396-411.
    13. Tasgin, Mursel & Bingol, Haluk O., 2019. "Community detection using boundary nodes in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 315-324.
    14. Wang, Tao & Yin, Liyan & Wang, Xiaoxia, 2018. "A community detection method based on local similarity and degree clustering information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 1344-1354.
    15. Chen, Naiyue & Liu, Yun & Chen, Haiqiang & Cheng, Junjun, 2017. "Detecting communities in social networks using label propagation with information entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 788-798.
    16. Zhang, Xiaolei & Ren, Yibin & Huang, Baoxiang & Han, Yong, 2018. "Analysis of time-varying characteristics of bus weighted complex network in Qingdao based on boarding passenger volume," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 376-394.
    17. Zhang, Weitong & Zhang, Rui & Shang, Ronghua & Li, Juanfei & Jiao, Licheng, 2019. "Application of natural computation inspired method in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 130-150.

    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:486:y:2017:i:c:p:31-43. 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.