Loading…

Evolutionary method for finding communities in bipartite networks

An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2011-06, Vol.83 (6 Pt 2), p.066120-066120, Article 066120
Main Authors: Zhan, Weihua, Zhang, Zhongzhi, Guan, Jihong, Zhou, Shuigeng
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03
cites cdi_FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03
container_end_page 066120
container_issue 6 Pt 2
container_start_page 066120
container_title Physical review. E, Statistical, nonlinear, and soft matter physics
container_volume 83
creator Zhan, Weihua
Zhang, Zhongzhi
Guan, Jihong
Zhou, Shuigeng
description An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.
doi_str_mv 10.1103/physreve.83.066120
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_889454681</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>889454681</sourcerecordid><originalsourceid>FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03</originalsourceid><addsrcrecordid>eNo9kD1PwzAYhC0EoqXwBxhQNqYUf8SxM1ZV-ZAqgRDMVmK_oYYkDrZT1H9Pqhamu-HupHsQuiZ4Tghmd_1mFzxsYS7ZHOc5ofgETQnnOKVM5Kd7z4qUCc4n6CKET4wZZTI7RxNKRCEynk3RYrV1zRCt60q_S1qIG2eS2vmktp2x3UeiXdsOnY0WQmK7pLJ96aONkHQQf5z_CpforC6bAFdHnaH3-9Xb8jFdPz88LRfrVGeExlSUEnMOZZ5xnkNRUFMVgkkwRBOBDZaGMiqAaiMyVjKTE13UVSZwpmkta8xm6Paw23v3PUCIqrVBQ9OUHbghKCmL8VEuyZikh6T2LoyEatV7247_FMFqT069jOReYbtSkqkDubF0c5wfqhbMf-UPFfsFSdVsJw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>889454681</pqid></control><display><type>article</type><title>Evolutionary method for finding communities in bipartite networks</title><source>American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)</source><creator>Zhan, Weihua ; Zhang, Zhongzhi ; Guan, Jihong ; Zhou, Shuigeng</creator><creatorcontrib>Zhan, Weihua ; Zhang, Zhongzhi ; Guan, Jihong ; Zhou, Shuigeng</creatorcontrib><description>An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.</description><identifier>ISSN: 1539-3755</identifier><identifier>EISSN: 1550-2376</identifier><identifier>DOI: 10.1103/physreve.83.066120</identifier><identifier>PMID: 21797454</identifier><language>eng</language><publisher>United States</publisher><subject>Algorithms ; Biological Evolution ; Commerce ; Genetic Loci - genetics ; Genetics ; Mutation ; Social Support</subject><ispartof>Physical review. E, Statistical, nonlinear, and soft matter physics, 2011-06, Vol.83 (6 Pt 2), p.066120-066120, Article 066120</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03</citedby><cites>FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/21797454$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Zhan, Weihua</creatorcontrib><creatorcontrib>Zhang, Zhongzhi</creatorcontrib><creatorcontrib>Guan, Jihong</creatorcontrib><creatorcontrib>Zhou, Shuigeng</creatorcontrib><title>Evolutionary method for finding communities in bipartite networks</title><title>Physical review. E, Statistical, nonlinear, and soft matter physics</title><addtitle>Phys Rev E Stat Nonlin Soft Matter Phys</addtitle><description>An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.</description><subject>Algorithms</subject><subject>Biological Evolution</subject><subject>Commerce</subject><subject>Genetic Loci - genetics</subject><subject>Genetics</subject><subject>Mutation</subject><subject>Social Support</subject><issn>1539-3755</issn><issn>1550-2376</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2011</creationdate><recordtype>article</recordtype><recordid>eNo9kD1PwzAYhC0EoqXwBxhQNqYUf8SxM1ZV-ZAqgRDMVmK_oYYkDrZT1H9Pqhamu-HupHsQuiZ4Tghmd_1mFzxsYS7ZHOc5ofgETQnnOKVM5Kd7z4qUCc4n6CKET4wZZTI7RxNKRCEynk3RYrV1zRCt60q_S1qIG2eS2vmktp2x3UeiXdsOnY0WQmK7pLJ96aONkHQQf5z_CpforC6bAFdHnaH3-9Xb8jFdPz88LRfrVGeExlSUEnMOZZ5xnkNRUFMVgkkwRBOBDZaGMiqAaiMyVjKTE13UVSZwpmkta8xm6Paw23v3PUCIqrVBQ9OUHbghKCmL8VEuyZikh6T2LoyEatV7247_FMFqT069jOReYbtSkqkDubF0c5wfqhbMf-UPFfsFSdVsJw</recordid><startdate>20110630</startdate><enddate>20110630</enddate><creator>Zhan, Weihua</creator><creator>Zhang, Zhongzhi</creator><creator>Guan, Jihong</creator><creator>Zhou, Shuigeng</creator><scope>CGR</scope><scope>CUY</scope><scope>CVF</scope><scope>ECM</scope><scope>EIF</scope><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope></search><sort><creationdate>20110630</creationdate><title>Evolutionary method for finding communities in bipartite networks</title><author>Zhan, Weihua ; Zhang, Zhongzhi ; Guan, Jihong ; Zhou, Shuigeng</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2011</creationdate><topic>Algorithms</topic><topic>Biological Evolution</topic><topic>Commerce</topic><topic>Genetic Loci - genetics</topic><topic>Genetics</topic><topic>Mutation</topic><topic>Social Support</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Zhan, Weihua</creatorcontrib><creatorcontrib>Zhang, Zhongzhi</creatorcontrib><creatorcontrib>Guan, Jihong</creatorcontrib><creatorcontrib>Zhou, Shuigeng</creatorcontrib><collection>Medline</collection><collection>MEDLINE</collection><collection>MEDLINE (Ovid)</collection><collection>MEDLINE</collection><collection>MEDLINE</collection><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><jtitle>Physical review. E, Statistical, nonlinear, and soft matter physics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Zhan, Weihua</au><au>Zhang, Zhongzhi</au><au>Guan, Jihong</au><au>Zhou, Shuigeng</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Evolutionary method for finding communities in bipartite networks</atitle><jtitle>Physical review. E, Statistical, nonlinear, and soft matter physics</jtitle><addtitle>Phys Rev E Stat Nonlin Soft Matter Phys</addtitle><date>2011-06-30</date><risdate>2011</risdate><volume>83</volume><issue>6 Pt 2</issue><spage>066120</spage><epage>066120</epage><pages>066120-066120</pages><artnum>066120</artnum><issn>1539-3755</issn><eissn>1550-2376</eissn><abstract>An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.</abstract><cop>United States</cop><pmid>21797454</pmid><doi>10.1103/physreve.83.066120</doi><tpages>1</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1539-3755
ispartof Physical review. E, Statistical, nonlinear, and soft matter physics, 2011-06, Vol.83 (6 Pt 2), p.066120-066120, Article 066120
issn 1539-3755
1550-2376
language eng
recordid cdi_proquest_miscellaneous_889454681
source American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)
subjects Algorithms
Biological Evolution
Commerce
Genetic Loci - genetics
Genetics
Mutation
Social Support
title Evolutionary method for finding communities in bipartite networks
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-07T13%3A04%3A08IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Evolutionary%20method%20for%20finding%20communities%20in%20bipartite%20networks&rft.jtitle=Physical%20review.%20E,%20Statistical,%20nonlinear,%20and%20soft%20matter%20physics&rft.au=Zhan,%20Weihua&rft.date=2011-06-30&rft.volume=83&rft.issue=6%20Pt%202&rft.spage=066120&rft.epage=066120&rft.pages=066120-066120&rft.artnum=066120&rft.issn=1539-3755&rft.eissn=1550-2376&rft_id=info:doi/10.1103/physreve.83.066120&rft_dat=%3Cproquest_cross%3E889454681%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c412t-7a8055ea64556e992db9738ed1c170d08d2327e2cd743a3d61c9fb4704c2f8f03%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=889454681&rft_id=info:pmid/21797454&rfr_iscdi=true