Networks in many real-world applications come with an inherent uncertainty in their structure, due to, for example, noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs have attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role. In this article, we study the problem of ( k , γ)-truss indexing and querying over an uncertain graph \({\mathcal {G}}\) . A ( k , γ)-truss is the largest subgraph of \({\mathcal {G}}\) such that the probability of each edge being contained in at least k -2 triangles is no less than γ. Our first proposal, CPT-index, keeps all the ( kz , γ)-trusses: retrieval for any given k and γ can be executed in an optimal linear time w.r.t. the graph size of the queried ( k , γ)-truss. We develop a bottom-up CPT-indexconstruction scheme and an improved algorithm for fast CPT-indexconstruction using top-down graph partitions. For trading off between ( k ,γ)-truss offline indexing and online querying, we further develop an approximate indexing approach ε , Δ r -APXequipped with two parameters, ε and Δ r , that govern tolerated errors. In addition, we further investigate the problem of maintaining ( k , γ)-truss indexes over dynamic uncertain graphs, where the update of vertex/edge insertions/deletions and also edge probability increments/decrements may frequently occur. We propose a comprehensive solution for CPT-indexand (ε , Δ r -APXmaintenance by addressing one fundamental task of one edge’s probability increment/decrement. To reduce the scope of affected edges that have trussness changed, we categorize three types of candidate edges and propose tight lower/upper bounds for trussness refinement, which can efficiently accomplish CPT-indexmaintenance in a local update scheme. Our proposed techniques for one single edge change can also be extended to handle a batch update of multiple edges. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms, as well as our ( k ,γ)-truss index maintenance algorithms, against state-of-the-art methods. Case studies on real-world graphs demonstrate the significant efficiency improvement by our proposed solutions as well as interesting discoveries.

A cohesive subgraph of k-truss requires that each edge has at least$(k-2)$triangles, which has wide applications of modeling social communities and complex network visualization. Recently, the study of truss maximization has gained attention, which aims to enlarge$k$-truss most by inserting$b$new edges into a graph$G$. However, existing maximization methods suffer from a stiff strategy of complete truss conversion, that is either converting the whole$(k-1)$-truss component to k-truss or converting no edge to k-truss without using any budget. To tackle this bottleneck, we develop a novel partial conversion strategy to explore more insertion plans. Based on partial conversion strategy, we revisit the problem of truss maximization in this paper and propose adaptive solutions by achieving more new k-truss edges. Specifically, we first decompose all$(k-1)$-truss into a series of disjoint components via the triangle connectivity, where each component's conversion is independent to each other. Then, for each$(k-1)$-truss component, we explore possible insertion plans of partial conversions. An intuitive method is to randomly insert a budget no more than$b$new edges and check the expected profit of new$k$-truss edges. Obviously, this method is inefficient due to a large search space of edge insertions and many times of expensive$k$-truss verification. To improve it, we propose a new minimum-cut based approach, which converts a subgraph of$(k-1)$-truss component into a flow graph with weighted edges and finds a key of maximum-flow answer corresponding to a k-truss conversion plan with the minimum budget consumption. Next, we develop a new dynamic programming framework to find the best way to allocate the budget$b$to all components. We design two fast dynamic programming algorithms and analyze the complexities theoretically. In addition, we explore the case of a large given budget$b$and extend our techniques to handle the conversion of$(k-h)$-truss into$k$-truss for$2\leq h\leq k-2$. Extensive experiment results demonstrate the superiority of our algorithms against the state-of-the-art methods.

K-truss is a useful notion of dense subgraphs, which can represent cohesive parts of a graph in a hierarchical way. In practice, in order to enable various truss-based applications to answer queries faster, the edge trussnesses are computed in advance. However, real-world graphs may not always be static and often have edges inserted or removed, leading to costly truss maintenance of recomputing all edge trussnesses. In this paper, we focus on dynamic graphs with star insertions/deletions, where a star insertion can represent a newly joined user with friend connections in social networks or a recently published paper with cited references in citation networks. To tackle such star-based truss maintenance, we propose a new structure of AffBall based on the local structure of an inserted/deleted star motif. With AffBall, we make use of the correlation of inserted edges to compute the trussnesses of the inner edges surrounding the star. Then, we analyze the onion layer of k-truss and conduct truss maintenance for the edges beyond the star, which can be efficiently achieved with a time complexity related to the number of the edges that change the onion layer. Moreover, we extend star-based truss maintenance to handle general updates and single-edge insertions/deletions. Extensive experiments on real-world dynamic graphs verify the effectiveness and efficiency of proposed algorithms against state-of-the-art truss maintenance algorithms.

Cohesive substructure identification is one fundamental task of graph analytics. Recently, a useful problem of dense subgraph maximization has attracted significant attentions, which aims at enlarging a dense subgraph pattern using a few new edge insertions, e.g., k-core maximization. As a more cohesive subgraph of k-core, k-truss requires that each edge has at least k-2 triangles within this subgraph. However, the problem of k-truss maximization has not been studied yet. In this paper, we motivate and formulate a new problem of budget-constrained k-truss maximization. Given a budget of b edges and an integer k≥2, the problem is to find and insert b new edges into a graph G such that the resulted k-truss of G is maximized. We theoretically prove the NP-hardness of k-truss maximization problem. To efficiently tackle it, we analyze non-submodular property of k-truss newcomers function and develop non-conventional heuristic strategies for edge insertions. We first identify high-quality candidate edges with regard to (k-1)-light subgraphs and propose a greedy algorithm using per-edge insertion. Besides further improving the efficiency by pruning disqualified candidate edges, we finally develop a component-based dynamic programming algorithm for enlarging k-truss mostly, which makes a balance of budget assignment and inserts multiple edges simultaneously into all (k-1)-light components. Extensive experiments on nine real-world graphs demonstrate the efficiency and effectiveness of our proposed methods.

Networks in many real-world applications come with an inherent uncertainty in their structure, due to e.g., noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs has attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role.