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.

In the era of big data, sensor networks have been pervasively deployed, producing a large amount of data for various applications. However, because sensor networks are usually placed in hostile environments, managing the huge volume of data is a very challenging issue. In this study, we mainly focus on the data storage reliability problem in heterogeneous wireless sensor networks where robust storage nodes are deployed in sensor networks and data redundancy is utilized through coding techniques. To minimize data delivery and data storage costs, we design an algorithm to jointly optimize data routing and storage node deployment. The problem can be formulated as a binary nonlinear combinatorial optimization problem, and due to its NP-hardness, designing approximation algorithms is highly nontrivial. By leveraging the Markov approximation framework, we elaborately design an efficient algorithm driven by a continuous-time Markov chain to schedule the deployment of the storage node and corresponding routing strategy. We also perform extensive simulations to verify the efficacy of our algorithm.

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.

In the Internet of Things (IoT), various battery-powered wireless devices are connected to collect and exchange data, and typical traffic is periodic and heterogeneous. Polling with power management is a very promising technique that can be used for communication among these devices in the IoT. In this paper, we propose a novel and scalable model to study the delay and the power consumption performance for polling schemes with power management under heterogeneous settings (particularly the heterogeneous sleeping interval). In our model, by introducing the concept of virtual polling interval, we successfully convert the considered energy-efficient polling scheme into an equivalent purely-limited vacation system. Thus, we can easily evaluate the mean and variance of the delay and the power consumption by applying existing queueing formulae, without developing a new theoretical model as required in previous works. Extensive simulations show that our analytical results are very accurate for both homogeneous and heterogeneous settings.