Large-scale graphs usually exhibit global sparsity with local cohesiveness, and mining the representative cohesive subgraphs is a fundamental problem in graph analysis. The $k$-truss is one of the most commonly studied cohesive subgraphs, in which each edge is formed in at least $k\mathrm{-}\mathrm{2}$ triangles. A critical issue in mining a $k$-truss lies in the computation of the trussness of each edge, which is the maximum value of $k$ that an edge can be in a $k$-truss. Existing works mostly focus on truss computation in static graphs by sequential models. However, the graphs are constantly changing dynamically in the real world. We study distributed truss computation in dynamic graphs in this paper. In particular, we compute the trussness of edges based on the local nature of the $k$-truss in a synchronized node-centric distributed model. Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm. Moreover, the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation. Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.

The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining. In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs, only very few indexes are proposed for the same in bipartite graphs. In this work, we present the index called $\alpha \mathsf{}\mathrm{(}\beta \mathrm{)}$-core number on vertices, which reflects the maximal cohesive and dense subgraph a vertex can be in, to help enumerate the $\mathrm{(}\alpha \mathrm{,}\beta \mathrm{)}$-cores, a commonly used dense structure in bipartite graphs. To address the problem of extremely high time and space cost for enumerating the $\mathrm{(}\alpha \mathrm{,}\beta \mathrm{)}$-cores, we first present a linear time and space algorithm for computing the $\alpha \mathsf{}\mathrm{(}\beta \mathrm{)}$-core numbers of vertices. We further propose core maintenance algorithms, to update the core numbers of vertices when a graph changes by avoiding recalculations. Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.

A public-private-graph (pp-graph) is developed to model social networks with hidden relationships, and it consists of one public graph in which edges are visible to all users, and multiple private graphs in which edges are only visible to its endpoint users. In contrast with conventional graphs where the edges can be visible to all users, it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph. In this paper, we first propose a novel concept, public-private-core (pp-core) number based on the k-core number, which integrally considers both the public graph and private graphs of vertices, to measure how critical a user is. We then give an efficient algorithm for the pp-core number computation, which takes only linear time and space. Considering that the graphs can be always evolving over time, we also present effective algorithms for pp-core maintenance after the graph changes, avoiding redundant re-computation of pp-core number. Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability. Compared to recalculating the pp-core numbers of all vertices, our maintenance algorithms can reduce the computation time by about 6–8 orders of magnitude.

Community search has been extensively studied in large networks, such as Protein-Protein Interaction (PPI) networks, citation graphs, and collaboration networks. However, in terms of widely existing multi-valued networks, where each node has $d$ ( $d\mathrm{⩾}\mathrm{1}$) numerical attributes, almost all existing algorithms either completely ignore the attributes of node at all or only consider one attribute. To solve this problem, the concept of skyline community was presented, based on the concepts of $k$-core and skyline recently. The skyline community is defined as a maximal $k$-core that satisfies some influence constraints, which is very useful in depicting the communities that are not dominated by other communities in multi-valued networks. However, the algorithms proposed on skyline community search can only work in the special case that the nodes have different values on each attribute, and the computation complexity degrades exponentially as the number of attributes increases. In this work, we turn our attention to the general scenario where multiple nodes may have the same attribute value. Specifically, we first present an algorithm, called MICS, which can find all skyline communities in a multi-valued network. To improve computation efficiency, we then propose a dimension reduction based algorithm, called P-MICS, using the maximum entropy method. Our algorithm can significantly reduce the skyline community searching time, while is still able to find almost all cohesive skyline communities. Extensive experiments on real-world datasets demonstrate the efficiency and effectiveness of our algorithms.