9
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      COMICS: a community property-based triangle motif clustering scheme

      research-article

      Read this article at

      ScienceOpenPublisherPMC
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          With the development of science and technology, network scales of various fields have experienced an amazing growth. Networks in the fields of biology, economics and society contain rich hidden information of human beings in the form of connectivity structures. Network analysis is generally modeled as network partition and community detection problems. In this paper, we construct a community property-based triangle motif clustering scheme (COMICS) containing a series of high efficient graph partition procedures and triangle motif-based clustering techniques. In COMICS, four network cutting conditions are considered based on the network connectivity. We first divide the large-scale networks into many dense subgraphs under the cutting conditions before leveraging triangle motifs to refine and specify the partition results. To demonstrate the superiority of our method, we implement the experiments on three large-scale networks, including two co-authorship networks (the American Physical Society (APS) and the Microsoft Academic Graph (MAG)), and two social networks (Facebook and gemsec-Deezer networks). We then use two clustering metrics, compactness and separation, to illustrate the accuracy and runtime of clustering results. A case study is further carried out on APS and MAG data sets, in which we construct a connection between network structures and statistical data with triangle motifs. Results show that our method outperforms others in both runtime and accuracy, and the triangle motif structures can bridge network structures and statistical data in the academic collaboration area.

          Most cited references49

          • Record: found
          • Abstract: found
          • Article: not found

          Modularity and community structure in networks

          M. Newman (2006)
          Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as "modularity" over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            Community structure in social and biological networks.

            A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known--a collaboration network and a food web--and find that it detects significant and informative community divisions in both cases.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Network motifs: simple building blocks of complex networks.

              Complex networks are studied across many fields of science. To uncover their structural design principles, we defined "network motifs," patterns of interconnections occurring in complex networks at numbers that are significantly higher than those in randomized networks. We found such motifs in networks from biochemistry, neurobiology, ecology, and engineering. The motifs shared by ecological food webs were distinct from the motifs shared by the genetic networks of Escherichia coli and Saccharomyces cerevisiae or from those found in the World Wide Web. Similar motifs were found in networks that perform information processing, even though they describe elements as different as biomolecules within a cell and synaptic connections between neurons in Caenorhabditis elegans. Motifs may thus define universal classes of networks. This approach may uncover the basic building blocks of most networks.
                Bookmark

                Author and article information

                Contributors
                Journal
                PeerJ Comput Sci
                PeerJ Comput Sci
                peerj-cs
                peerj-cs
                PeerJ Computer Science
                PeerJ Inc. (San Diego, USA )
                2376-5992
                11 March 2019
                2019
                : 5
                : e180
                Affiliations
                [1 ]School of Software, Dalian University of Technology , Dalian, China
                [2 ]State Key Laboratory for Novel Software Technology, Nanjing University , Nanjing, China
                Author information
                http://orcid.org/0000-0003-1124-9509
                Article
                cs-180
                10.7717/peerj-cs.180
                7924480
                b7bcb6c1-b73c-479d-998f-02f04ea5d64f
                © 2019 Feng et al.

                This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited.

                History
                : 3 December 2018
                : 9 February 2019
                Funding
                Funded by: China Postdoctoral Science Foundation
                Award ID: 2018T110210
                Funded by: State Key Laboratory for Novel Software Technology, Nanjing University
                Award ID: KFKT2018B04
                This work is supported by China Postdoctoral Science Foundation under Grant 2018T110210 and State Key Laboratory for Novel Software Technology, Nanjing University, under Grant KFKT2018B04. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
                Categories
                Algorithms and Analysis of Algorithms
                Graphics
                Network Science and Online Social Networks

                community property,triangle motif,large network,clustering

                Comments

                Comment on this article