Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"Dense subgraph"”.
-
Dense subgraph mining in probabilistic graphs
… we consider the problem of mining cohesive (dense) subgraphs in probabilistic graphs, where each edge has a probability of existence. Mining probabilistic graphs has become the focus of interest in analyzing many real-world datasets, such as social, trust, communication, and biological …
-
Dense subgraph discovery: novel algorithms and applications
Dense subgraph discovery (DSD) is an important technique for analyzing and extracting valuable insights from large-scale graph data across various fields, including social sciences, biology, and chemistry. Lying at the core of DSD is the densest subgraph problem (DSP), which finds the subgraph that …
-
Dense subgraph detection on multi-layered networks
Dense subgraph detection is a fundamental building block for a variety of applications. Most of the existing methods aim to discover dense subgraphs within a single network, or within a multi-view network consisting of a common set of nodes. However, many real-world applications can be better …
-
Incremental and parallel algorithms for dense subgraph mining
<p>The task of maintaining densely connected subgraphs from a continuously evolving graph is important because it solves many practical problems that require constant monitoring over the continuous stream of linked data often represented as a graph. For example, continuous maintenance of a certain …
-
Alternating Optimization for the Dense Subgraph and Submatrix Problems
… We look at new heuristics to solve the Dense Submatrix problem as a model problem for clustering. We propose a new convex relaxation model for this problem, and then reformulate the problem as a non-convex quadratic program. We apply the Alternating Direction Method of Multipliers, the …
-
Empirical Comparison of Statistical Tests of Dense Subgraph in Network Data
… One type of community structure of interest is a dense subgraph. Statistically deciding whether a network contains a dense subgraph can be formulated as a hypothesis test where under the null hypothesis, there is no community structure, and under the alternative hypothesis, the network contains a …
-
Applications of Gaussian boson sampling in graph theory
… hard problems, including dense subgraph finding, a problem which repre-<br/>sents difficult tasks in various fields, from finance to drug discovery.<br/>In this thesis, we consider evidence for Gaussian boson sampling showing a performance<br/>or time advantage for certain …
-
STREAMING ANOMALY DETECTION
… graph data, and to reduce detecting suspicious dense subgraph problem to finding a dense submatrix in constant time. Next, we broaden the graph setting to multi-aspect data. We propose MStream which detects anomalies in multi-aspect data streams including both categorical and numeric attributes. …
-
Dual algorithms for the densest subgraph problem
Dense subgraph discovery is an important primitive for many real-world graph mining applications. The dissertation tackles the densest subgraph problem via its dual linear programming formulation. Particularly, our contributions in this thesis are the following: (i) We give a faster width-dependent …
-
Dense graph pattern mining and visualization
… most research attention, and it is called the dense subgraphs. A dense subgraph (pattern) is one class of critical information within a graph that represents a high level of interactions among entities. Such high level of interactions in many applications implies outstanding level of …
-
Learning COVID-19 network from literature databases using core decomposition
… on the extended network and identify dense subgraphs. We then evaluate the identified dense subgraph and the generated hypotheses in three contexts: literature validation for uncovered virus targeting genes and proteins, gene function enrichment analysis on subgraphs, and literature …
-
NEW STATISTICAL METHODS FOR HIGH-DIMENSIONAL DATA WITH COMPLEX STRUCTURES
… 2, we develop a likelihood-based adaptive dense subgraph discovery (ADSD) procedure to identify connectomic subnetworks (subgraphs) that are systematically associated with brain disorders. We propose the statistical inference procedure leveraging graph properties and combinatorics. We …
-
Methods, algorithms and impossibility results for machine learning on graphs
… edge-diverse and rich in small-sized dense subgraphs. We show the limitations of edge independent graph generative models and develop a hierarchy of models that are progressively more powerful in terms of mimicking better real-world networks. We complement our analysis with simple …
-
Finding Interesting Subgraphs with Guarantees
… network data, such as anomaly detection, dense subgraph mining, motif finding, information diffusion, and epidemic spread. A common underlying task in all these problems is finding an "interesting subgraph"; that is, finding a part of the graph---usually small relative to the whole---that …
-
Graph-based Inference with Constraints for Object Detection and Segmentation
… the hough-voting framework with finding dense subgraph inference. Compared to previous work, we propose a novel shape matching scheme suitable for partial matching of edge fragments. The shape descriptor has the same geometric units as shape context but our shape representation is not …
-
Methods for analyzing temporal networks
… of discovering a set of nodes, which forms a dense subgraph and whose interactions occur in short time intervals. This formulation provides an accurate representation of dense overlapping communities and their dynamics over the network history. For all proposed novel problems we present …
-
Combining combinatorial and LP-based methods for better and faster approximation algorithms
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms
-
Analyzing The Community Structure Of Web-like Networks: Models And Algorithms
… shown that many such networks have a locally dense and globally sparse structure with certain small, dense subgraphs occurring much more frequently than they do in the classical Erdös-Rényi random graphs. This peculiarity--which is commonly referred to as community structure--has been observed …
-
Finding Dense Regions of Rapidly Changing Graphs
… internal structure---hierarchies of locally dense regions---and finding and tracking this structure is key to detecting emerging behavior, exposing internal activity, summarizing for downstream tasks, identifying important regions, and more. Existing techniques to track these regions …
-
Statistical inference on network data
… of those networks. The problem of finding densely connected subgraphs in a network has attracted a lot of recent attention. Such subgraphs are sometimes referred to as communities in social networks or molecular modules in protein networks. In Chapter 4, we propose two Monte Carlo …