COMICS: a community property-based triangle motif clustering scheme COMICS: a community property-based triangle motif clustering scheme Yufan Feng1, Shuo Yu1, Kaiyuan Zhang1, Xiangli Li1 and Zhaolong Ning1,2 1 School of Software, Dalian University of Technology, Dalian, China 2 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China 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. Subjects Algorithms and Analysis of Algorithms, Graphics, Network Science and Online Social Networks Keywords Community property, Triangle motif, Large network, Clustering INTRODUCTION In all aspects of human endeavor, we are in the world of large-scale data, embracing the aspects of biology, medicine, social, traffic, and science (Ning et al., 2017). These data sets describe the complicated real-world systems from various and complementary viewpoints. Generally, the entities in real-world systems are modeled as nodes, whose connections and relationships are modeled as edges. Those networks become new carriers of rich information from domain-specific areas, such as the reciprocity among people in online social networks (Koll, Li & Fu, 2013). More than that, human beings are inclined to cooperate or participate in group activities, which can be reflected in social and academic collaboration networks. To be more specific, in academic area, big scholarly data grows rapidly, containing millions of authors, papers, citations, figures, tables, and other How to cite this article Feng Y, Yu S, Zhang K, Li X, Ning Z. 2019. COMICS: a community property-based triangle motif clustering scheme. PeerJ Comput. Sci. 5:e180 DOI 10.7717/peerj-cs.180 Submitted 3 December 2018 Accepted 9 February 2019 Published 11 March 2019 Corresponding author Zhaolong Ning, zhaolongning@dlut.edu.cn Academic editor Yilun Shang Additional Information and Declarations can be found on page 19 DOI 10.7717/peerj-cs.180 Copyright 2019 Feng et al. Distributed under Creative Commons CC-BY 4.0 http://dx.doi.org/10.7717/peerj-cs.180 mailto:zhaolongning@�dlut.�edu.�cn https://peerj.com/academic-boards/editors/ https://peerj.com/academic-boards/editors/ http://dx.doi.org/10.7717/peerj-cs.180 http://www.creativecommons.org/licenses/by/4.0/ http://www.creativecommons.org/licenses/by/4.0/ https://peerj.com/computer-science/ massive scale related data, such as digital libraries and scholarly networks (Xia et al., 2017). As collaboration behaviors among scholars are becoming frequent, collaboration networks are generally in large-scale and contain rich collaboration information, reflecting the cooperation patterns among scholars in different research areas. Bordons et al. (1996) regard the academic teams as scientists communities, in which scholars can share research methods, materials, and financial resources rather than institutions organized by fixed structures (Barjak & Robinson, 2008). Furthermore, the ternary closures in social networks constitute a minimal stable structure; that is, a loop with three nodes. The number of ternary closures in social networks changes over time, which reveals the evolvement of human social behaviors. Besides, the definition of a clustering coefficient is based on the distributions of ternary closures. Milo et al. (2002) defined small network structures as motifs to present interconnections in complex networks by numbers that are significantly higher than those in randomized networks. Motifs can define universal classes of networks, and researchers are carrying on the motif detection experiments on networks from different areas, such as biochemistry, neurobiology, and engineering, to uncover the existence of motifs and the corresponding structure information in networks (Ribeiro, Silva & Kaiser, 2009; Bian & Zhang, 2016). Hence, triangle motifs can be used to uncover relationships in networks. Connectivity is a fundamental character in both graph theory and network science. When networks are in small-scale, the dense areas can be easily identified. However, with the rapid growth of network scale and diversity, many graph partition methods, community detection, and clustering algorithms fail to uncover the information of graph structure. Graph partition and mining algorithms consume a large amount of time when dealing with large-scale networks, for example, the gSpan algorithm (Yan & Han, 2002) and the Min–Cut algorithm (Stoer & Wagner, 1997), which overlook the elementary network structures. The clusters and subgraphs of a large network are generally have small internal distances and large external distances among nodes. Considering the ternary closures, triangle network motifs have been regarded as elementary units in networks. However, a general method to cluster the communities and analyze the relationships with community properties and triangle motifs effectively is still lacking. In this paper, we propose a community property-based triangle motif clustering scheme (COMICS) to cluster network communities, and analyze the relationships with triangle motifs. In this method, we partition networks with the edge connection properties and regard the undirected and unweighted complete triangle motifs as the element clustering units. The partition operations are based on four network cutting conditions, whose definitions are based on the network connectivity to maintain the massive links in networks. More than that, by considering the American Physical Society (APS) and Microsoft Academic Graph (MAG) data sets in the academic analysis area, we regard each cluster generated from the input network as an academic team, and define three metrics: teamwork of collaborator variance (TCV), teamwork of paper variance (TPV), and motif variances of scholars (MSV) to evaluate the Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 2/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ behaviors of the detected academic teams. Our contributions can be summarized as follows: � By jointly considering time complexity and clustering accuracy, we construct the COMICS, which mines the structure information with complete triangle motifs. A series of speed-up and refining methods, graph partition and refining techniques, are integrated to improve the performance of the basic clustering process. � We prove the time complexity of the presented algorithm is O(rn3), where r is the number of the clustered subgraphs from the original large network, and n is the number of nodes. � We regard the undirected and unweight complete triangle motif as the elementary unit instead of nodes in the clustering procedure. Our work verifies that the complete triangle motif is available in network analysis. � We define three metrics to analyze the hidden information in academic collaboration networks. Performance evaluations show that the academic teams with high quantity of scholar motif variances also have high values of TCVs. The roadmap of this paper is illustrated as follows. We briefly illustrate the related works in the following section. After that, a series of fundamental definitions, problem statement, and some necessary notations are described. Then, we describe the architecture of COMICS in details. We evaluate the performance of our method with three large-scale networks as case studies in the experiment section. Finally, we conclude this paper. RELATED WORK Information mining from large-scale networks is a significant research topic, reflecting the connecting patterns, and the social relationships among different entities (Shi et al., 2017; Schaeffer, 2007). In collaboration networks, the information reflects the collaboration patterns and academic social relationships among scholars in different disciplines. Community detection is traditionally considered as a kind of graph partition to discover exhaustive and disjoined node clusters in a given network (Khan et al., 2017). The discovery of structures in networks has attracted scholars’ attentions for a long time. The authors in Leskovec et al. (2009) explore from a novel perspective to identify meaningful communities in large social and information networks. They notice that large networks have very different structures. For example, different transcription networks from Escherichia coli and Saccharomyces cerevisiae have large differences in the frequency motif structures (Wegner, 2014). Over the past years, a number of graph clustering methods have been investigated. For example, evolutionary algorithms (EAs) have been proposed and applied successfully in the network optimization and clustering problems (Gong et al., 2012). Recently, scholars have successfully developed both single- and multi-objective EAs to discover internal structure information of networks (Li & Liu, 2016; Pizzuti, 2012). A particle swarm optimization algorithm is put forward, which reveals community structures in large-scale social networks (Cai et al., 2015). In Girvan & Newman (2002), node centrality and betweeness centrality were used to extract Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 3/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ communities in a network. Since modularity is becoming very popular by partitioning networks into non-overlapping subgraphs, modularity score, compactness-isolation, and other criteria are leveraged to evaluate functions in large graph partition problems Bagrow (2008). A number of large-scale partition methods based on community detection start with a given seed, and then expand by iteratively adding the neighboring node that contributes most to the score function, until the score function stops improving (Luo, Wang & Promislow, 2008; Ma et al., 2014). The authors in Du et al. (2007) developed an efficient community detection method in social networks, which combines the topological information with the entity attributions to detect network communities. However, this method works for merely part of network structures. Motifs in networks are small connected subnetworks, occurring in significant high frequencies and have recently gathered attentions. Motifs in networks have been studied as elementary structures in complex network analysis (Shervashidze et al., 2009). In hypergraphs, the clustering algorithms mainly focus on transforming the hypergraphs into simple graphs (Zhou, Huang & Schölkopf, 2006). Then, the simple graphs can be clustered with spectral clustering procedures based on the normalized Laplacian matrices (Li & Milenkovic, 2017). In that case, the motifs can be constructed with nodes from different graph layers of hypergraphs (Zhou, Huang & Schölkopf, 2006), for example, a triangle motif can be used to represent one heterogeneous hypergraph with three different layers. More than that, conductance is a vital definition in spectral clustering (Louis, 2015; Li & Milenkovic, 2018). Hence, in large-scale networks, spectral clustering and motif are combined to large-scale network clustering. Triangle motif structures guarantee the structural connections. The motif-based conductance ensures the applicability spectral clustering in large-scale networks. Some local graph clustering methods have been investigated by incorporating high-order network information captured by small subgraphs (Yin et al., 2017; Lee, Gharan & Trevisan, 2014; Li et al., 2017b). In Wegner (2014), the authors define a subgraph cover to represent the network with motifs. The cover consists of a set of motifs and their corresponding frequencies. Besides, the network motifs can be detected by comparing the frequencies of subgraphs in the original network with a statistical model. The authors in Wegner (2014) notice that real networks contain significant densities of different motifs. It illustrates networks in different fields hold different collaboration patterns, and motifs are the fingerprints of different networks. By observing the characteristics from real networks, Benson, Gleich & Leskovec (2016) develop a generalized framework to cluster networks on basis of higher-order connected patterns. A framework is proposed to model the relations between higher-order motif instances and graph nodes with a bipartite graph (Li et al., 2017a). In Monti, Otness & Bronstein (2018), MotifNet is introduced to deal with directed graphs by exploiting local graph motifs. In order to tackle the graph analysis problem, we combine the graph partition method with the motif-based clustering procedure to speed up the clustering process. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 4/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ System model and problem formulation In this section, we present basic theoretical definitions about cutting conditions and the mathematical expressions of motifs. After that, we describe the investigated problems in details. Comparative conditions for cluster In this subsection, we introduce four conditions to partition the original large collaboration networks into different clusters. For a given graph G = (V, E), we define the adjacent matrix H = {hi,j} as: if there exists an edge between vertices i and j, hi,j = 1; otherwise, hi,j = 0. Network partition is defined as: P ¼ fG1; G2; . . . ; Gkg; 1 � k � jVj, subject to: (1) SK k¼1 Gk ¼ V, (2) Gk \ Gt ¼ [, ∀k s t, and (3) Gk 6¼ [; 8k. For ∀k, the partition P satisfies the x—valid condition, called x—valid cluster partition of G, and x is defined as the following conditions according to Lu et al. (2013): Condition 1 : X 8j2Gk Hi;j > X 8j2VnGk Hi;j; 8i 2 Gk; 8k: (1) Condition 2 : X 8j2Gk Hi;j > X 8j2Gt Hi;j; 8i 2 Gk; k 6¼ t: (2) Condition 3 : X 8j2Gk Hi;j > X 8i2Gk;8j2VnGk Hi;j; 8k: (3) Condition 4 : X 8j2Gk Hi;j > X 8i2Gk;8j2Gt Hi;j; 8k 6¼ t: (4) Conditions 1 and 2 check the validity of clusters at the vertex level to confirm whether the internal degree of each vertex is larger than that of the external degree. Conditions 3 and 4 check the validity of clusters, that is, comparing the total internal degree of each cluster. When large graphs are partitioned under the above-mentioned four conditions, Condition 1 generally results in fewer, but larger subgraphs; Condition 4 will lead to more and smaller communities; Conditions 2 and 3 will cause more and smaller communities than Condition 1, but fewer and larger communities than Condition 4. Definitions of network triangle motifs In real networks, the most common high-order structures are small network subgraphs, which are defined as motifs, that is, a set of edges with a small number of nodes. In this paper, we analyze undirected triangular motif-based networks. Formally, we define a triangle motif by a tuple (B, A), where B is a 3 � 3 binary matrix and A � f1; 2; � � � ; ng is the set of anchor nodes. The matrix B encodes the edge pattern between the three nodes in triangle motifs, and A represents a relevant subset of nodes to define motif conductance. Then, let wA be a selection function, taking the subset of a 3-tuple induced by A. Define set (·) as the operator, which takes a tuple to a set, set (v1, v2, v3) = {v1, v2, v3}. Then, the motif set of an unweighted and undirected graph with adjacency matrix A can be denoted by Eq. (5), where v1 s v2 s v3, Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 5/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ Tri ðB; AÞ ¼ fset ðvÞ; set ðvAðvÞÞjv 2 Vk; Av ¼ Bg: (5) Here, Av is the k � k adjacency matrix of the subgraph with k nodes of the order vector v. In this paper, the motifs are undirected and unweighted. The matrix B of motif is symmetrical. Hence, we use (v, wA(v)) to denote (set (v), set (wA(v))) for convenience. Furthermore, we regard any (v, wA(v)) ∈ Tri (B, A) as a motif instance. If A and B are arbitrary or clear from context, we simply denote the motif set by Tri. We define the motifs, that is, wA(v) = v, as simple motifs, and others are anchor motifs. We give an example of triangle motif definition, as shown in Fig. 1, aiming to cluster the given five-node network by the two triangle motifs. First, we define the motifs by the description in Eq. (5). For motif Tri1, there are two instances of the motifs in G. Meanwhile, for motif Tri2, G has three instances, and the anchor sets of each instance is the node whose degree is one. The definition of the triangle motif conductance replaces an edge with a motif instance of type Tri. We suppose that a given network has been clustered into two subnetworks, that is, g and �g, and the conductance based on motifs can be expressed in Eq. (6), c ðGÞ Tri ðSÞ ¼ ðcutðGÞTri ðg; �gÞÞ minðvolðGÞTri ðgÞ; vol ðGÞ Tri ð�gÞÞ : (6) When there is at least one anchor node in S and at least one anchor node exists in �g, a motif instance can be cut. In Eq. (6), cut ðGÞ Tri ðg; �gÞ is the number of instance cut. vol ðGÞ Tri ðgÞ is the number of instances, whose end nodes are in g. To be more specific, following the definition of Tri in Eq. (5), as for the same wA(v), there may exist many different values of v, and nodes in wA(v) are still counted proportionally into the number of motif instances. This growth tendency of motifs is consistent with the number of nodes in networks. This can prove the availability of motifs in clustering networks. Definition of motif-base matrices Given a graph and a set of motif Tri, the motif adjacency matrix WTri of graph is shown as: ðWTriÞij ¼ X ððv;vAðvÞÞ2TriÞ 1 ðfi; jg � vAðvÞji 6¼ jÞ: (7) Herein, (WTri)ij is the number of motif instances in M, where nodes i and j are both in a triangle motif. In other words, the weight will be added into (WTri)ij if and only if node i Figure 1 Example of motif definition in diagram: the motifs Tri1 and Tri2 are leveraged to detect in the five-node graph G on the left figure. The motifs are defined by a binary matrix B and an anchor set of nodes. B1 and B2 are the binary matrices of Tri1 and Tri2, respectively. Similarly, A1 and A2 are the anchor node sets of Tri1 and Tri2, respectively. Full-size DOI: 10.7717/peerj-cs.180/fig-1 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 6/22 http://dx.doi.org/10.7717/peerj-cs.180/fig-1 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ and node j both appear in the anchor set. In the collaboration networks, (WTri)ij depends on the number of scholars, who collaborate with both scholar i and scholar j. Then, the motif diagonal degree matrix DM is defined as ðDTriÞii ¼ Pn j¼1 ðWTriÞij. The motif Laplacian can be calculated by LTri = DTri - WTri. Finally, we normalize the motif Laplacian as: �Tri ¼ I � D�1=2Tri WTriD �1=2 Tri : (8) Problem statement Let G = (V, E) be a connected large network, where V is the node set, and E is the edge set. If G contains several disjoint networks, it can be expressed as G = {G1, G2, ⋯, Gn}. The complete triangle is the target motif to analyze the large-scale networks. Our objective is to find the dense and stable disjoined subgraph set P ¼ fG001; G002; . .. ; G00mg of the given network by motifs. Given a node v ∈ V in the network Gi ∈ G, the degree of v is denoted by deg(v) and the neighbor node set of the subgraph Gi in the original networks is denoted by NGi. In the partition phase, Gi can be cutted into a set of subgraphs, G 0 i1; G 0 i2; . . . ; G 0 ikf g. For a node v in a partition subgraph G0ij of Gi, we use deginter(v) and degextra(v) to represent the degree within G0ij and the number of edges between G 0 ij and Gi=G 0 ij, respectively. Con(G 0 ij) is the set of subgraphs that are connected with G0ij in the partition P. Variable Q is the modularity score when the original graph G gets the partition P. In the process of graph partition, we cut the original networks into initial subgraphs under the four conditions. In that way, the network can be cutted into subgraphs with strong internal connectivity and weak external connectivity in both local and global aspects. The modularity score refining subprocedure can optimize the partition. Then, we cluster and analyze the initial dense subgraphs by the complete triangle motif. COMICS algorithm In this section, we describe the whole process of our COMICS in details. As shown in Fig. 2, COMICS consists of a series of partition refine strategies and a motif-based clustering procedure, that is, graph partition, modularity refine procedure and motif-based Figure 2 Architecture of COMICS. Full-size DOI: 10.7717/peerj-cs.180/fig-2 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 7/22 http://dx.doi.org/10.7717/peerj-cs.180/fig-2 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ clustering procedure. We first illustrate the graph partition techniques under four conditions and the modularity refine procedure in Algorithm 1. After that, the motif-based clustering procedure is constructed on each subgraph in cutting set. We specify the whole clustering layer algorithm in Algorithm 4, by which we are able to get the close and stable subgraph structures from the original input networks. Graph partition and modularity refine procedures To obtain the total information of large networks effectively, we first perform cutting operations in large networks. In this subsection, we explain the graph partition and modularity refine procedures in details. We use the total large graph as the input of the partition procedure, and the procedure returns a set of partition subgraphs of the original graph. The subgraph set is refined in the modularity refine procedure by modularity score. In the graph partition procedure, we take the differences between the internal and external degrees as the degree difference value of a node v, denoted by D(v), that is, DðvÞ ¼ deginterðvÞ � degextraðvÞ: (9) For all pairs of nodes v and u in networks, if nodes v and u fall in the same subgraph, the quantity of svsu is 1, otherwise, it equals to -1. |E| is the total number of edges in the original network. The value of ev, u is 1, if there exists one edge between nodes v and u, otherwise it is 0. Therefore, the modularity score of a network is defined as Eq. (10): Q ¼ 1 4jEj X v;u � ev;u � deg vð Þdeg uð Þ 2jEj � ðsvsu þ 1Þ: (10) Algorithm 1 Graph Partition Algorithm Input: Large graph G, conditions Output: R: A partition set P of G 1: Add G to R 2: while |R| increases and Rj j 6¼ 1 do 3: for each subgraph Gi in R do 4: \\ rootG0ij is a node from Gi. A new subgraph G 0 ij can be generated from Gi with rootG0ij . 5: rootG0ij ¼ argmin v 2 V deg vð Þf g 6: for node v in NðG0ijÞ do 7: if v satisfies the given conditions then 8: Add node to G0ij 9: else 10: rootG0ij ¼ argmin v 2 V D vð Þf g 11: end if 12: end for 13: Make the partition G0ij=Gi; Gi � � 14: end for 15: end while 16: return R Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 8/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ As described in Algorithm 1, we take the large networks and the cutting conditions as the input of the graph partition procedure. At the beginning of this procedure, there is only one original graph added in the result partition set R. The number of subgraphs in R is represented as |R|. In each outer loop, each subgraph Gi is chosen to generate new subgraphs, G0ij. Hence, the root node of the new subgraph G 0 ij is selected randomly among the nodes that are with the minimum degree of the new subgraph in R. As described in lines 6–12, the loop aims to generate the new graph from the root node from Gi. If at least one neighbor node of the total new subgraph satisfies the validity of the input conditions, the neighbor node is added to the new subgraph G0ij with its connectivity; otherwise, it means that there is no neighbor with this root node, and we select a new node in Gi as the root to check the connectivity with the original network. The node with the minimum difference between the internal and external degrees will be the root node of G0ij. Then, graph partition operations will be carried until no other nodes from the original networks satisfy the cutting condition. In line 3 of Algorithm 1, there are two cases when selecting a new root node of the new subgraph: one is that the root node selected in line 4 or line 9 has no neighbor, that is, the degree of root node is 0. It indicates the root node vroot is invalid, and no new subgraph can be added into R. The other situation is that there is no node in G connected with the partition subgraph. In other words, the iteration of adding nodes to the new subgraph stops. Then a new subgraph generated by the root node vroot is added to the subgraph set R. The iteration of the partition procedure stops when the number of subgraphs in R does not increase any more. However, if there exists one graph in R all the time, it illustrates that the root node with the minimum degree is invalid, and we have to choose another root node and restart the iteration. Algorithm 1 cuts large graph into small dense subgraphs. Each loop generates a new subgraph from set R, and the loop stops when no more dense subgraph can be found. To avoid damaging the connectivity of the rest nodes, we check the connectivity of both cutting and remaining parts, if there exists more than one component, we put all subgraphs in set R to the modularity refine procedure in Algorithm 2. The modularity refine procedure described in Algorithm 2 takes the results of the Algorithm 1 as input to refine the partition results of the original networks. As shown in Algorithm 2, lines 1 and 2 enumerate two connected subgraphs: G0ij and G 0 ik in R. In the following line 3 to line 6, if the two subgraphs are combined to one, it results in much higher modularity score than the original network partition. Then we replace G0ij and G 0 ik by G 0 ij [ G0ik, and the iteration stops until the modularity scores do not increase any more. Variable R0 is the result set of Algorithm 2, containing a series of refined subgraphs. This procedure of graph partition aims to maintain more structure information of the original large-scare networks, so that the output partition by Algorithm 2 can achieve higher modularity score than the input subgraph set. The operation of merging these two cutting subgraphs increases the internal degrees. Merging two subgraphs into one can also decrease the external degree for the subgraphs in partition P. If two subgraphs can be merged, the number of edges between them is larger than that cannot be Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 9/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ merged. Then as long as the two subgraphs are merged, the external degree of the input network can be reduced. Triangle motif-based clustering procedure We take the subgraph set of the original network as the input of the motif-based clustering procedure. As shown in Algorithm 3, its main idea is to find a single cluster in a graph by leveraging target motifs. In this procedure, we cluster the subgraphs in R by the minimum conductance, aiming to find the most stable part with the highest conductance of the given subgraph. The algorithm outputs a partition of nodes in g and �g. The motif conductance is symmetric in the sense that c ðGÞ Tri ðGNodeÞ ¼ c ðGÞ Tri ð�GNodeÞ, so that any set of nodes (g and �g) can be interpreted as a cluster. However, it is common that one set is substantially smaller than the other in practice. We take the larger set as a module in the network. Some networks are clustered for specific motivations, such as mining the relationships of a person in the social networks. In that case, Algorithm 3 takes the larger part in the clustering results g and �g as the cluster results as shown from line 9 to line 12. In the process of the motif-based clustering, we take the target motif and a subgraph partitioned in R (the output of Algorithm 2) as the input. As shown in Fig. 3, for a given graph and a target motif, we calculate a series of matrices, that is, WTri, DTri, and �Tri, before weighting the input graph of matrix WTri. Therefore, the graph is cut by the minimum conductance c ðGÞ Tri expressed in Eq. (6). In line 8 of Algorithm 3, the value of c ðGÞ Tri is determined by a series of sorted eigenvalues of the subgraph’s motif Laplacian matrix �Tri. Between the two cut subgraphs of the input graph, the larger one will be chosen as the output result. Combined COMICS algorithm In this subsection, we describe the overall algorithm of COMICS in Algorithm 4. It combines all three subprocedures in this subsection. Algorithm 2 Modularity Refine Algorithm Input: Subgraphs set R, empty set R0 Output: Refined subgraphs set R0 1: for G0ij in R do 2: for G0ik in Con Gijð Þ do 3: if Q G0ij [ G0ik � � > Q G0ij � � then 4: G00ij ¼ G0ij [ G0ik 5: Remove Gij and G0ik from R 6: Add G00ij to R0 7: end if 8: end for 9: end for 10: return R0 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 10/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ We take the large-scale networks, target motifs and the given validity conditions as the algorithm input, and obtain the clustering set of the original input network. At beginning, a series of partition and refining operations are carried on input networks under the valid conditions. Then we get a partition with high modularity scores of the original input large networks. Each subgraph in the partition set has a strong internal connectivity and a weak external connectivity, maintaining the stable structure information of the original network. Furthermore, we carry the motif-based clustering operations on the subgraph in the partition set. Finally, we can get the non-overlapping optimal partition of the original graph. Time complexity analysis In this section, we analyze the time complexity of COMICS. The main clustering layer includes the following three phases: graph partition, graph refining and motif-clustering. Algorithm 3 Triangle Motif-based Clustering Algorithm Input: Graph G and motif Tri Output: Subgraph set of the original network 1: (WTri)ij = number of triangle motif instances of Tri 2: GTri ) weighted graph induced WTri 3: DTri = diagonal matrix with ðDTriÞii ¼ Pn j¼1 ðWTriÞij 4: �Tri ¼ I � D�1=2Tri WTriD �1=2 Tri 5: z = eigenvector of second smallest eigenvalue for �Tri 6: ri = to be the index of D ðð�1Þ=2Þ Tri 7: z = ith smallest value 8: g ¼ argminl cðGÞTri ðGlNodeÞ; where l ¼ s1; � � � ; sk 9: if gj j > �gj j then 10: return g 11: else 12: return �g 13: end if Figure 3 Triangle motif-based clustering of COMICS. Full-size DOI: 10.7717/peerj-cs.180/fig-3 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 11/22 http://dx.doi.org/10.7717/peerj-cs.180/fig-3 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ We assume m and n as the number of edges and nodes in the network. Here, d(v) is the degree of node v and dmax is the maximal degree in the network. Graph partition procedure: To get and parse the information from large networks effectively, we first apply cutting operations on the large-scale networks. We analyze the worst case of the graph partition subprocedure. In the first cutting iteration, the root node is one of the nodes with the smallest degree in the graph, and its time complexity is O(n). For each new subgraph g generated by root node v, we check the connectivity of the new-added nodes, including the internal and external links with subgraph g and check the corresponding conditions before partitioning. The time complexity of this procedure is Oðn2d2maxÞ. Modularity refining procedure: In the subgraph refining procedure, we use modularity score Q (Newman, 2006) to get a suitable partition. The required time of iterations is up to the number of subgraphs in the result sets R, which are generated by the graph partition procedure. We define the number of subgraphs in R as p, and the runtime of the procedure is determined by the step of calculating Q, whose computation complexity is O[(m + n)n]. Because the first refining subgraph need to check the other p - 1 subgraphs and the second one checks the remaining p - 2. Hence, the total checking times is p2/2. Therefore, the computation complexity of the refining procedure is O[p2(m + n)n/2]. Triangle motif-based clustering procedure: In general, the time complexity of the algorithm is determined by the construction of the adjacency matrix and the solution of the eigenvector. For simplicity, we consider that we can access network edges within O(1), and modify matrix entries within O(1). The complexity of calculating the eigenvectors through Laplacian matrix is O((m + n) (log n)O(1)), and sorting the eigenvector indexes can be finished in time O(n log n). For a motif with three nodes, we can compute WM in �(n 3) in a complete graph with n nodes. Therefore, the computation complexity of the motif-based analysis procedure is O(n3). According to the description above, the time complexity of COMICS is O(rn3), where r is the number of subgraphs in the partition set R, and n is the number of nodes. EXPERIMENTS In this section, we compare COMICS with K-means and co-authorship team detection algorithm from the perspectives of network clustering accuracy and time complexity, Algorithm 4 Combined COMICS Algorithm Input: Large graph G, conditions and motif Tri Output: Motif-based cluster set (subset of nodes in G) 1: Set R1 as an empty set 2: R = Graph Partition Algorithm(G, conditions) 3: R0 = Modularity Refine Algorithm(R) 4: for g in R0 do 5: g0 = Triangle Motif-based Clustering Algorithm(g, Tri) 6: Add g0 to R1 7: end for 8: return R1 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 12/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ respectively. We choose four large-scale networks, including two social network, that is, Facebook and gemsec-Deezer data sets (Leskovec & Krevl, 2014; Rozemberczki et al., 2018) and two academic collaboration networks, that is, APS and MAG data sets. We analyze the accuracy of the clustering results by calculating compactness and separation. We demonstrate the efficiency of our solution in both academic collaboration and social networks. We also consider other statistical data information of academic networks, TCVs, TPVs, and MSV. All those corresponding metrics are illustrated in this section. All experiments are conducted on a desktop with Intel(R) Xeon(R) CPU E5-2690 v3 @ 2.60 GHz (two processors) and 128 GB memory. The operating system is Window 10, and the codes are written in python. The American Physical Society data set (2009–2013) consists of 96,908 papers associated with 159,724 scholars in the physical field. Meanwhile, the MAG data set (1980–2015) on computer science includes 207,432 scholars with 84,147 papers in the computer science area. Edges in the academic networks represent two authors have coauthored at least one paper. The Facebook social network data set in our experiments contains eight networks, 134,833 nodes and 1,380,293 edges. We list the eight social networks in Table 1. In that case, we cluster the social networks by the different categories listed in the data set. Gemsec-Deezer data set collected by Deezer (November 2017) is also experimentalized in this paper. This data set contains 143,884 nodes and 846,915 edges from three countries, Romania (41,773 nodes and 125,826 edges), Croatia (54,573 nodes and 498,202 edges) and Hungray (47,538 nodes and 222,887 edges). Experiment settings In this subsection, we describe the settings of our experiments from three aspects, that is, time cost, clustering accuracy and academic teamwork behavior analysis with complete triangle motif in academic areas. In academic collaboration networks, we consider two algorithms. The Facebook social networks do not contain any statistical information. Therefore, we merely compare our method with K-means algorithm in the social network: K-means clustering algorithm (Ding & He, 2004): This method proves that principal components are the continuous solutions to cluster membership indicators for K-means clustering. It takes principal component analysis into the clustering process, which is suitable for the scholar science and social data sets. Co-authorship algorithm (Reyes-Gonzalez, Gonzalez-Brambila & Veloso, 2016): This algorithm considers all the principal investigators and collaborators, and defines Table 1 Facebook date sets. TV shows Politician Government Public figures Node 3,892 5,908 7,057 11,565 Edge 17,262 41,729 89,455 67,114 Athletes Company New Sites Artist Node 13,866 14,113 27,917 50,515 Edge 86,858 52,310 206,259 819,306 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 13/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ knowledge footprints1 of the groups to calculate the distances between scholars and the group. Based on the distance, the academic groups can be detected in an accurate way. This method iterates all the researchers with their collaborator and institution similarities until they are assigned to a academic team can be applied to understand the self-organizing of research teams and obtain the better assessment of their performances. To demonstrate the runtime efficiency and the accuracy of our clustering results in large-scale networks, we divide the APS and MAG data sets into different parts with various sizes by years, respectively, so that we can get the collaboration networks with distinct number of nodes (from 1,000 to 200,000). Considering the integrality and veracity of the academic research teams in data sets, we take the whole APS and MAG data sets as the collaboration networks to detect the collaborative relationships. Evaluation metrics To evaluate and analyze the accuracy of network clustering results of our proposed COMICS, we use two metrics, that is, compactness and separation, to evaluate node closeness in clustering results and the distances among clusters. In academic collaboration networks, we combine the statistical paper publishing data with network structures together, and calculate three metrics to find the characteristics discovered through the target triangle motif to uncover the hidden collaboration patterns and teamwork of scholars in academic networks. Compactness and separation (Halkidi, Batistakis & Vazirgiannis, 2002) are used to evaluate the accuracy of clustering results by different methods. Compactness is a widely used metric to quantify the tightness of clustering subgraphs, representing the distances between nodes in a subgraph. Separation calculates the distances among the cores of different subgraphs. That is, if a clustering subgraph is with lower compactness value and higher separation value, the subgraph can be detected effectively. Compactness is expressed by Eq. (11), Compactness ¼ 1 Rj j X vi2� vi � wj j: (11) Here, R is the clustering result set, vi is one of the nodes in the subgraph, and w is defined as the core of the subgraph cluster, because w is the node with the maximum degree in a cluster. The value of |vi - w| means the shortest distance between node vi and the cluster core node w. SP is defined as in Eq. (12). Separation ¼ 2 k2 � k Xk i¼1 Xk j¼iþ1 jwi � wjj; (12) wherein, k is the number of subgraphs in the result set and wi is the core of the given subgraph i, which is the same as wj. The value of |wi - wj| equals to the shortest distance between wi and wj. 1 knowledge footprints of a group are the union of all the backward citations used by group members in all of their papers within a specific time period. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 14/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ In collaboration networks, we assume the clusters as academic teams, in which scholars work together. Therefore, three metrics are defined to analyze the collaboration behaviors through triangle motif: TCV, TPV, and MSV. TCV: This metric reflects the tightness and volatility among members in a team. For one scholar i in a team, we define the TCV as follows, sco ¼ Pn i ðcoi � coaveÞ2 n : (13) Herein, n is the number of team members, coi is the number of scholars that scholar i has collaborated within the same team, and coave is the average number of collaborators collaborated with scholars in a team. TPV: An academic team with high performance refers that the members in team have published a large number of paper. Similarly, in a stable team, the gaps of published paper numbers among team members are small. To evaluate the academic levels and stability of a team, we define TPV as follows: sqtt ¼ Pn i ðqi � qaveÞ2 n ; (14) where sqtt means scholar i’s variance of publishing papers in the detected team, qi is the number of papers that scholar i has published, and qave is the average number of papers in the team. MSV: This metric calculates the difference of motif number that the scholar nodes are included in the collaboration networks. We define the MSV as follows, sprimitive ¼ Pn i ðti � taveÞ2 n : (15) Herein, ti is the number of target motif that scholar i owns, and tave is the average motifs of a team. To uncover the collaboration patterns mined by triangle motifs among scholars in academic teams, we use the above three arguments to analyze relationships between productions and motifs of the clustered academic teams. RESULTS AND DISCUSSION In this section, we evaluate the experimental results by comparing with K-means and co-authorship algorithm in both runtime and the effectiveness. In the view of internal and external connections, we calculate compactness and separation values for each algorithm results. The time cost results of three networks are shown in Tables 2–4, respectively. “K” in the tables represents thousand, for example, “1K” means a network with one thousand nodes. N/A means that the clustering procedure takes more than 5 days. According to Tables 2–4, it can be concluded that, in small networks (less than 30,000 nodes), the three methods make little differences in running time. However, as the size of network increases, our clustering algorithm costs the least time. The time costs in Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 15/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ different data sets make little differences. However, the results show the same trend and the proposed method takes more time in small networks and outperforms other large networks. As shown in Tables 2 and 3, when academic collaboration networks contain more than 30,000 nodes, COMICS takes the least time than the other two algorithms. More than that, in social networks, the time cost of our method is also satisfied in large size networks. Therefore, it can be concluded that though the partition operations cost a Table 2 APS runtime. COMICS Co-authorship K-means 1 K 36.32 s 2.12 s 1.73 s 3 K 435.67 s 17.45 s 207.06 s 10 K 3,058.21 s 1,084.83 s 3.47 h 30 K 1.03 h 2,856.47 s 5.73 h 50 K 1.83 h 4.82 h 13.36 h 80 K 2.29 h 9.87 h >24 h 120 K 5.46 h 16.36 h >24 h 150 K 9.97 h >24 h N/A Table 3 MAG runtime. COMICS Co-authorship K-means 1 K 24.74 s 3.79 s 2.04 s 3 K 343.17 s 21.05 s 237.93 s 10 K 2,956.64 s 345.29 s 3.53 h 30 K 1.08 h 2,636.95 s 6.62 h 50 K 2.47 h 2.93 h 12.48 h 80 K 3.35 h 4.07 h >24 h 120 K 5.09 h 8.27 h >24 h 150 K 8.91 h 21.83 h N/A 200 K 14.68 h >24 h N/A Table 4 Social network runtime. COMICS K-means TV shows 573.62 s 322.86 s Politician 1,394.05 s 786.42 s Government 1.03 h 2.71 h Public figures 1.26 h 1.60 h Athletes 1.58 h 2.04 h Company 0.98 h 3.07 h New sites 4.78 h 9.32 h Artist 6.89 h 23.42 h Romania 3.46 h 17.68 h Hungray 3.96 h 18.07 h Croatia 6.04 h 38.42 h Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 16/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ lot of time, it is necessary to apply the speeding up techniques in clustering. Moreover, for different types of networks, topological structures, density are also vital factors that can effect the clustering procedures and results. Figures 4A and 5A show the compactness values generated by our algorithm and the comparing algorithms on different sizes of networks, respectively. As the figures show, in collaboration networks, compactness values corresponding to different networks are lower than those in co-authorship algorithm and K-means algorithm, which are similar with that in social networks. Our algorithm performs better than the two comparing algorithms. Figures 4B and 5B plot the separation values of the three algorithms with the network growth in both academic, Facebook social and gemsec-Deezer networks. It can be seen that with the growing network size, COMICS achieves the highest separation values. This means subgraphs clustered by our method have greater separation values all the time. According to Figs. 4B and 5B, we can conclude that the distances among core nodes in each cluster are close no matter what algorithms are used. The reason is that no matter what algorithms are used in the target network, the core nodes of clusters are almost the same. All the core nodes are with the maximum degrees. In all, our clustering algorithm achieves the best subgraph clustering results obviously. Analysis in academic collaboration networks After analyzing the time complexity and effectiveness of our system above, in this subsection, we analyze the clustering results with the triangle motifs in academic collaboration networks. The results prove the triangle motif structures can reflect the hidden statistical information and connections with network structures. For example, as the analysis results show, collaboration patterns as well as the correlations of network structure and team productions can be summarized in the academic collaboration networks. We regard the cluster results of each academic collaboration network as an academic team. Then the values of three variances, that is, TPV, TCV, and MSV are calculated, and the results are shown in Figs. 6A and 6B. Hence, we can see that the number of high-order triangle motif can reflect the performance of an academic team to some extent. Figure 4 The variation tendency of compactness and separation values of collaboration network clustering results with COMICS, co-authorship and K-means algorithms. (A) Compactness in aca- demic collaboration networks and (B) separation in academic collaboration networks. Full-size DOI: 10.7717/peerj-cs.180/fig-4 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 17/22 http://dx.doi.org/10.7717/peerj-cs.180/fig-4 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ According to Figs. 6A and 6B, we conclude that the TPV and TCV are both proportional to the MSV. Meanwhile, the TPV is also approximately positive linear with the MSV. That means, the lower the MSV is in a cluster team, the performance of team members are in smaller gaps. Therefore, it can be concluded that the value of MSV can reflect the gap of collaboration relationships in teams and performance of team members. However, we can infer that the scholars with few number of complete triangle motifs, have collaborated with only few scholars in the team. Those scholars are probably students or new team members, resulting in the high collaboration and paper variances. Hence, in collaboration networks, we can use MSV to evaluate the gaps of team collaboration relationships and the performance of team members. The two teamwork gaps in different periods represent the stability and volatility of academic teams. CONCLUSION In this paper, we put forth the high-order motif-based clustering system to get a subgraph set from the large-scale networks. In the constructed system, we take graph partition and refining techniques to speed up algorithm runtime. Through network cutting, we check the Figure 5 The variation tendency of compactness and separation values of the clustering results in social networks with COMICS and K-means algorithms. (A) Compactness in social networks and (B) separation in social networks. Full-size DOI: 10.7717/peerj-cs.180/fig-5 Figure 6 Positive relations in collaboration networks through collaboration variances, paper variances and motif variances of each clustering. Red rectangles and blue triangles represent the col- laboration academic teams clustered from MAG and APS data sets, respectively. (A) Relationships between TCV and MSV and (B) relationships between TPV and MSV. Full-size DOI: 10.7717/peerj-cs.180/fig-6 Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 18/22 http://dx.doi.org/10.7717/peerj-cs.180/fig-5 http://dx.doi.org/10.7717/peerj-cs.180/fig-6 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ four cutting conditions from the aspect of network connectivity, which can prevent damaging the global structures of large-scale networks. Experiments are carried on four large networks, that is, APS and MAG from the academic area, Facebook and gecsec-Deezer networks from the social area, respectively. The results demonstrate the effectiveness of our method in time cost and accuracy in large-scale network clustering. Furthermore, the collaboration teamwork analysis verifies the availability of complete triangle motif, which represents the smallest collaboration unit in the collaboration networks. We analyze the collaboration clustering results with three metrics, that is, TCV, TPV, and MSV. The results show that both TCV and TPV are proportional to MSV. Therefore, it can be concluded that the value of MSV can reflect the two gaps, that is, collaborative relationships and performance of different team members. Besides, the two gaps in different periods can also reflect the dynamic change of team members. In the future, we will focus on dynamic motif clustering for real-time network management (Ning et al., 2018; Ning, Huang & Wang, 2019; Wang et al., 2018a). In addition, network security (Wang et al., 2018b, 2019) and crowdsourcing based methods (Ning et al., 2019a, 2019b) also deserve to be investigated. ADDITIONAL INFORMATION AND DECLARATIONS Funding 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. Grant Disclosures The following grant information was disclosed by the authors: China Postdoctoral Science Foundation: 2018T110210. State Key Laboratory for Novel Software Technology, Nanjing University: KFKT2018B04. Competing Interests The authors declare that they have no competing interests. Author Contributions � Yufan Feng conceived and designed the experiments, performed the experiments, analyzed the data, contributed reagents/materials/analysis tools, prepared figures and/or tables, authored or reviewed drafts of the paper, approved the final draft. � Shuo Yu conceived and designed the experiments. � Kaiyuan Zhang analyzed the data, contributed reagents/materials/analysis tools, performed the computation work. � Xiangli Li performed the experiments, analyzed the data, performed the computation work. � Zhaolong Ning conceived and designed the experiments, authored or reviewed drafts of the paper, approved the final draft. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 19/22 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ Data Availability The following information was supplied regarding data availability: Data is available through the American Physical Society (APS) and Microsoft Academic Graph (MAG). Specifically: Facebook network data can be found here: http://snap.stanford.edu/data/ego-Facebook.html. Gemsec-Deezer network data can be found here: http://snap.stanford.edu/data/gemsec- Deezer.html. Code can be found here: https://github.com/yffre/COMICS. REFERENCES Bagrow JP. 2008. Evaluating local community methods in networks. Journal of Statistical Mechanics: Theory and Experiment 2008(05):P05001 DOI 10.1088/1742-5468/2008/05/p05001. Barjak F, Robinson S. 2008. International collaboration, mobility and team diversity in the life sciences: impact on research performance. Social Geography 3(1):23–36 DOI 10.5194/sg-3-23-2008. Benson AR, Gleich DF, Leskovec J. 2016. Higher-order organization of complex networks. Science 353(6295):163–166 DOI 10.1126/science.aad9029. Bian X, Zhang K. 2016. Modeling network with topic model and triangle motif. In: Ubiquitous Intelligence and Computing and 2015 IEEE International Conference on Autonomic and Trusted Computing and 2015 IEEE International Conference on Scalable Computing and Communications and ITS Associated Workshops, Piscataway: IEEE, 880–886. Bordons M, Gomez I, Fernández M, Zulueta M, Méndez A. 1996. Local, domestic and international scientific collaboration in biomedical research. Scientometrics 37(2):279–295 DOI 10.1007/BF02093625. Cai Q, Gong M, Ma L, Ruan S, Yuan F, Jiao L. 2015. Greedy discrete particle swarm optimization for large-scale social network clustering. Information Sciences 316:503–516 DOI 10.1016/j.ins.2014.09.041. Ding C, He X. 2004. K-means clustering via principal component analysis. In: Proceedings of the Twenty-First International Conference on Machine Learning. Banff, Alberta: ACM, 29. Du N, Wu B, Pei X, Wang B, Xu L. 2007. Community detection in large-scale social networks. In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis. New York: ACM, 16–25. Girvan M, Newman ME. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America 99(12):7821–7826. Gong M, Ma L, Zhang Q, Jiao L. 2012. Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Physica A: Statistical Mechanics and Its Applications 391(15):4050–4060 DOI 10.1016/j.physa.2012.03.021. Halkidi M, Batistakis Y, Vazirgiannis M. 2002. Clustering validity checking methods: part ii. ACM SIGMOD Record 31(3):19–27 DOI 10.1145/601858.601862. Khan S, Liu X, Shakil KA, Alam M. 2017. A survey on scholarly data: from big data perspective. Information Processing & Management 53(4):923–944 DOI 10.1016/j.ipm.2017.03.006. Koll D, Li J, Fu X. 2013. With a little help from my friends: replica placement in decentralized online social networks. Technical Report TR-IFI-TB-2013-01, University of Goettingen, Germany. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 20/22 http://snap.stanford.edu/data/ego-Facebook.html http://snap.stanford.edu/data/gemsec-Deezer.html http://snap.stanford.edu/data/gemsec-Deezer.html https://github.com/yffre/COMICS http://dx.doi.org/10.1088/1742-5468/2008/05/p05001 http://dx.doi.org/10.5194/sg-3-23-2008 http://dx.doi.org/10.1126/science.aad9029 http://dx.doi.org/10.1007/BF02093625 http://dx.doi.org/10.1016/j.ins.2014.09.041 http://dx.doi.org/10.1016/j.physa.2012.03.021 http://dx.doi.org/10.1145/601858.601862 http://dx.doi.org/10.1016/j.ipm.2017.03.006 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ Lee JR, Gharan SO, Trevisan L. 2014. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM 61(6):1–30 DOI 10.1145/2665063. Leskovec J, Krevl A. 2014. SNAP Datasets: Stanford large network dataset collection. Available at http://snap.stanford.edu/data. Leskovec J, Lang KJ, Dasgupta A, Mahoney MW. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6(1):29–123 DOI 10.1080/15427951.2009.10129177. Li P, Chen K, Ge Y, Zhang K, Small M. 2017a. Bipartite centrality diffusion: mining higher-order network structures via motif-vertex interactions. EPL (Europhysics Letters) 120(2):28003 DOI 10.1209/0295-5075/120/28003. Li P, Dau H, Puleo G, Milenkovic O. 2017b. Motif clustering and overlapping clustering for social network analysis. In: IEEE INFOCOM 2017—IEEE Conference on Computer Communications, Piscataway: IEEE, 1–9 DOI 10.1109/INFOCOM.2017.8056956. Li Z, Liu J. 2016. A multi-agent genetic algorithm for community detection in complex networks. Physica A: Statistical Mechanics and Its Applications 449:336–347. Li P, Milenkovic O. 2017. Inhomogeneous hypergraph clustering with applications. In: Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems 30. Long Beach: Curran Associates, Inc., 2308–2318. Li P, Milenkovic O. 2018. Submodular hypergraphs: p-Laplacians, cheeger inequalities and spectral clustering. arXiv e-prints. Louis A. 2015. Hypergraph markov operators, eigenvalues and approximation algorithms. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ‘15. New York: ACM, 713–722. Lu Z, Wu W, Chen W, Zhong J, Bi Y, Gao Z. 2013. The maximum community partition problem in networks. Discrete Mathematics, Algorithms and Applications 5(4):1350031 DOI 10.1142/s1793830913500316. Luo F, Wang JZ, Promislow E. 2008. Exploring local community structures in large networks. Web Intelligence and Agent Systems: An International Journal 6(4):387–400. Ma L, Huang H, He Q, Chiew K, Liu Z. 2014. Toward seed-insensitive solutions to local community detection. Journal of Intelligent Information Systems 43(1):183–203 DOI 10.1007/s10844-014-0315-6. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. 2002. Network motifs: simple building blocks of complex networks. Science 298(5594):824–827 DOI 10.1126/science.298.5594.824. Monti F, Otness K, Bronstein MM. 2018. Motifnet: A motif-based graph convolutional network for directed graphs. arXiv Preprint DOI 10.1109/DSW.2018.8439897. Newman ME. 2006. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America 103(23):8577–8582 DOI 10.1073/pnas.0601602103. Ning Z, Dong P, Kong X, Xia F. 2018. A cooperative partial computation offloading scheme for mobile edge computing enabled internet of things. IEEE Internet of Things Journal 1 DOI 10.1109/JIOT.2018.2868616. Ning Z, Huang J, Wang X. 2019. Vehicular fog computing: enabling real-time traffic management for smart cities. IEEE Wireless Communications 26(1):87–93 DOI 10.1109/MWC.2019.1700441. Ning Z, Kong X, Xia F, Hou W, Wang X. 2019a. Green and sustainable cloud of things: enabling collaborative edge computing. IEEE Communications Magazine 57(1):72–78 DOI 10.1109/MCOM.2018.1700895. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 21/22 http://dx.doi.org/10.1145/2665063 http://snap.stanford.edu/data http://dx.doi.org/10.1080/15427951.2009.10129177 http://dx.doi.org/10.1209/0295-5075/120/28003 http://dx.doi.org/10.1109/INFOCOM.2017.8056956 http://dx.doi.org/10.1142/s1793830913500316 http://dx.doi.org/10.1007/s10844-014-0315-6 http://dx.doi.org/10.1126/science.298.5594.824 http://dx.doi.org/10.1109/DSW.2018.8439897 http://dx.doi.org/10.1073/pnas.0601602103 http://dx.doi.org/10.1109/JIOT.2018.2868616 http://dx.doi.org/10.1109/MWC.2019.1700441 http://dx.doi.org/10.1109/MCOM.2018.1700895 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ Ning Z, Wang X, Rodrigues J, Xia F. 2019b. Joint computation offloading, power allocation, and channel assignment for 5G-enabled traffic management systems. IEEE Transactions on Industrial Informatics 1 DOI 10.1109/TII.2019.2892767. Ning Z, Xia F, Ullah N, Kong X, Hu X. 2017. Vehicular social networks: enabling smart mobility. IEEE Communications Magazine 55(5):16–55 DOI 10.1109/mcom.2017.1600263s. Pizzuti C. 2012. A multiobjective genetic algorithm to find communities in complex networks. IEEE Transactions on Evolutionary Computation 16(3):418–430 DOI 10.1109/tevc.2011.2161090. Reyes-Gonzalez L, Gonzalez-Brambila CN, Veloso F. 2016. Using co-authorship and citation analysis to identify research groups: a new way to assess performance. Scientometrics 108(3):1171–1191 DOI 10.1007/s11192-016-2029-8. Ribeiro P, Silva F, Kaiser M. 2009. Strategies for network motifs discovery. In: E-Science, 2009. e-Science’09. Fifth IEEE International Conference. Piscataway: IEEE, 80–87. Rozemberczki B, Davies R, Sarkar R, Sutton C. 2018. Gemsec: graph embedding with self clustering. Available at http://arxiv.org/abs/1802.03997. Schaeffer SE. 2007. Graph clustering. Computer Science Review 1(1):27–64 DOI 10.1016/j.cosrev.2007.05.001. Shervashidze N, Vishwanathan S, Petri T, Mehlhorn K, Borgwardt K. 2009. Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, Clearwater Beach, Florida, USA, 488–495. Shi C, Li Y, Zhang J, Sun Y, Philip SY. 2017. A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering 29(1):17–37. Stoer M, Wagner F. 1997. A simple min-cut algorithm. Journal of the ACM 44(4):585–591 DOI 10.1145/263867.263872. Wang X, Ning Z, Hu X, Ngai EC-H, Wang L, Hu B, Kwok RYK. 2018a. A city-wide real-time traffic management system: enabling crowdsensing in social internet of vehicles. IEEE Communications Magazine 56(9):19–25 DOI 10.1109/MCOM.2018.1701065. Wang X, Ning Z, Zhou M, Hu X, Wang L, Zhang Y, Richard Yu F, Hu B. 2018b. Privacy- preserving content dissemination for vehicular social networks: challenges and solutions. IEEE Communications Surveys & Tutorials 1 DOI 10.1109/COMST.2018.2882064. Wang X, Ning Z, Hu X, Wang L, Hu B, Cheng J, Leung VCM. 2019. Optimizing content dissemination for real-time traffic management in large-scale internet of vehicle systems. IEEE Transactions on Vehicular Technology 68(2):1093–1105 DOI 10.1109/TVT.2018.2886010. Wegner AE. 2014. Subgraph covers: an information-theoretic approach to motif analysis in networks. Physical Review X 4(4):041026 DOI 10.1103/physrevx.4.041026. Xia F, Wang W, Bekele TM, Liu H. 2017. Big scholarly data: a survey. IEEE Transactions on Big Data 3(1):18–35 DOI 10.1109/tbdata.2016.2641460. Yan X, Han J. 2002. gspan: Graph-based substructure pattern mining. In: Data Mining, 2002. ICDM 2003. Proceedings 2002 IEEE International Conference. Maebashi: IEEE, 721–724. Yin H, Benson AR, Leskovec J, Gleich DF. 2017. Local higher-order graph clustering. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 555–564. Zhou D, Huang J, Schölkopf B. 2006. Learning with hypergraphs: clustering, classification, and embedding. In: International Conference on Neural Information Processing Systems, Canada, Vol. 19, 1601–1608. Feng et al. (2019), PeerJ Comput. Sci., DOI 10.7717/peerj-cs.180 22/22 http://dx.doi.org/10.1109/TII.2019.2892767 http://dx.doi.org/10.1109/mcom.2017.1600263s http://dx.doi.org/10.1109/tevc.2011.2161090 http://dx.doi.org/10.1007/s11192-016-2029-8 http://arxiv.org/abs/1802.03997 http://dx.doi.org/10.1016/j.cosrev.2007.05.001 http://dx.doi.org/10.1145/263867.263872 http://dx.doi.org/10.1109/MCOM.2018.1701065 http://dx.doi.org/10.1109/COMST.2018.2882064 http://dx.doi.org/10.1109/TVT.2018.2886010 http://dx.doi.org/10.1103/physrevx.4.041026 http://dx.doi.org/10.1109/tbdata.2016.2641460 http://dx.doi.org/10.7717/peerj-cs.180 https://peerj.com/computer-science/ COMICS: a community property-based triangle motif clustering scheme Introduction Related Work Experiments Results and Discussion Conclusion References << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.4 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile (None) /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages false /ColorImageDownsampleType /Average /ColorImageResolution 300 /ColorImageDepth 8 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /FlateEncode /AutoFilterColorImages false /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages false /GrayImageDownsampleType /Average /GrayImageResolution 300 /GrayImageDepth 8 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /FlateEncode /AutoFilterGrayImages false /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages false /MonoImageDownsampleType /Average /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /CHS /CHT /DAN /DEU /ESP /FRA /ITA /JPN /KOR /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR /PTB /SUO /SVE /ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /NoConversion /DestinationProfileName () /DestinationProfileSelector /NA /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure true /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles true /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /NA /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /LeaveUntagged /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice