Open Access Issue
Distributed Truss Computation in Dynamic Graphs
Tsinghua Science and Technology 2023, 28 (5): 873-887
Published: 19 May 2023
Abstract PDF (7 MB) Collect

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-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.

Open Access Issue
Core Decomposition and Maintenance in Bipartite Graphs
Tsinghua Science and Technology 2023, 28 (2): 292-309
Published: 29 September 2022
Abstract PDF (2 MB) Collect

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 α(β)-core number on vertices, which reflects the maximal cohesive and dense subgraph a vertex can be in, to help enumerate the (α,β)-cores, a commonly used dense structure in bipartite graphs. To address the problem of extremely high time and space cost for enumerating the (α,β)-cores, we first present a linear time and space algorithm for computing the α(β)-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.

Regular Paper Issue
Generous or Selfish? Weighing Transaction Forwarding Against Malicious Attacks in Payment Channel Networks
Journal of Computer Science and Technology 2022, 37 (4): 888-905
Published: 25 July 2022
Abstract Collect

Scalability has long been a major challenge of cryptocurrency systems, which is mainly caused by the delay in reaching consensus when processing transactions on-chain. As an effective mitigation approach, the payment channel networks (PCNs) enable private channels among blockchain nodes to process transactions off-chain, relieving long-time waiting for the online transaction confirmation. The state-of-the-art studies of PCN focus on improving the efficiency and availability via optimizing routing, scheduling, and initial deposits, as well as preventing the system from security and privacy attacks. However, the behavioral decision dynamics of blockchain nodes under potential malicious attacks is largely neglected. To fill this gap, we employ the game theory to study the characteristics of channel interactions from both the micro and macro perspectives under the situation of channel depletion attacks. Our study is progressive, as we conduct the game-theoretic analysis of node behavioral characteristics from individuals to the whole population of PCN. Our analysis is complementary, since we utilize not only the classic game theory with the complete rationality assumption, but also the evolutionary game theory considering the limited rationality of players to portray the evolution of PCN. The results of numerous simulation experiments verify the effectiveness of our analysis.

Open Access Issue
Distributed Consensus for Blockchains in Internet-of-Things Networks
Tsinghua Science and Technology 2022, 27 (5): 817-831
Published: 17 March 2022
Abstract PDF (4.6 MB) Collect

In recent years, due to the wide implementation of mobile agents, the Internet-of-Things (IoT) networks have been applied in several real-life scenarios, servicing applications in the areas of public safety, proximity-based services, and fog computing. Meanwhile, when more complex tasks are processed in IoT networks, demands on identity authentication, certifiable traceability, and privacy protection for services in IoT networks increase. Building a blockchain system in IoT networks can greatly satisfy such demands. However, the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions, especially in terms of achieving consensus on each block in complex wireless environments, which directly motivates our work. In this study, we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks, including the negative impacts caused by contention and interference in wireless channel, and the lack of reliable transmissions and prior network organizations. By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks, we showed that it is possible to directly reach a consensus for blockchains in IoT networks, without relying on any additional network layers or protocols to provide reliable and ordered communications. In our theoretical analysis, we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving. The extensive simulation results also validate our conclusions in the theoretical analysis.

Open Access Issue
Fast Skyline Community Search in Multi-Valued Networks
Big Data Mining and Analytics 2020, 3 (3): 171-180
Published: 16 July 2020
Abstract PDF (1.2 MB) Collect

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 ( d1) 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.

Total 5