Quantifying node importance on engagement dynamics is critical to support network stability. We can motivate or retain the users in a social platform according to their importance s.t. the network is more sustainable. Existing studies validate that the coreness of a node is the "best practice" on network topology to estimate the engagement of the node. In this paper, the importance of a node is the effect on the engagement of other nodes when its engagement is strengthened or weakened. Specifically, the importance of a node is quantified via two novel concepts: the anchor power to measure the engagement effect of node strengthening (i.e., the overall coreness gain) and the collapse power to measure the engagement effect of node weakening (i.e., the overall coreness loss). We find the computation of the two concepts can be naturally integrated into a shell component-based framework, and propose a unified static algorithm to compute both the anchored and collapsed followers. For evolving networks, efficient maintenance techniques are designed to update the follower sets of each node, which is faster than redoing the static algorithm by around 3 orders of magnitude. Extensive experiments on real-life data demonstrate the effectiveness of our model and the efficiency of our algorithms.

Multilayer graphs are very powerful in representing the multiplex relationships among entities. The truss decomposition on single-layer graphs is a well-studied problem which divides a graph into a hierarchy structure, and has a series of applications. However, little attention has been paid to the truss decomposition on multilayer graphs. In addition, truss decomposition on multilayer graphs derives new challenges compared to the scenario on single-layer graphs. In this paper, we devise an efficient algorithm to compute the truss decomposition on multilayer graphs. Extensive experiments on 5 real-life datasets validate the effectiveness and efficiency of our methods.

Graph pattern matching has been extensively investigated on general graphs without time information over decades. Nevertheless, few studies focus on temporal graphs, where a relationship between two vertices takes place at a specific moment and lingers for some time. In this paper, we propose a new notion so-calledtime-respecting flow graph, in which all paths are time-respecting (i.e., a sequence of contacts with non-decreasing time), and one vertex is distinguished as the root, from which other vertices can be reached via a time-respecting path. Based on this, we explore the problem oftime-respecting flow graph pattern matching on temporal graphs. This problem motivates important applications in epidemiology, information diffusion, crime detection, etc. To address it, we present one baseline algorithm as well as two optimized algorithms that utilize several efficient matching strategies and topological sort based technique to boost efficiency. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness and efficiency of our proposed algorithms. Compared with baseline method, our optimized algorithms could achieve up to three orders of magnitude speedup.

The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored k-core problem aims to enlarge the size of the k-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the "best practice" for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient heuristic algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithm is efficient.