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 60 for “"K-Core"”.
-
Parallel Discovery of Fixed-sized Connected k-Core Skyline Communities
… values of nodes. In this study, we focus on k-Core subgraphs, where every node has a degree of at least k, and look for those holding skyline properties. We propose both sequential and parallel algorithms for discovering skyline k-Core subgraphs and perform experiments to investigate how input …
-
The Maximum Anchored k-core Problem: Mixed Integer Programming Formulations
The maximum anchored k-core problem plays an important role in marketing, network architecture, and social media; the problem allows network designers and influencers to find the most pivotal vertices which increase the size of the network. In this thesis, we investigate two mixed integer …
-
The Closure of the Minimal k-core Problem for Modeling k-assemblies
… a backtracking algorithm to find all minimal k-cores of a given undirected graph, which belongs to the class of NP-hard problems. The proposed method is a modification of the Bron and Kerbosch algorithm for finding all cliques of an undirected graph. The minimal k-core problem has applications …
-
Stability and Application of the k-core Dynamical Model to Biological Networks
… is to illustrate the importance of the k-core dynamical model, by first presenting the stability analysis of the nonlinear k-core model and compare its solution to the most widely used linear model. Second, I show a real world application of the k-core model to describe properties of …
-
A Network Theoretical Approach to Real-World Problems: Application of the K-Core Algorithm to Various Systems
The study of complex networks is, at its core, an exploration of the mechanisms that control the world in which we live at every scale, from particles no bigger than a grain of sand and amino acids that comprise proteins, to social networks, ecosystems, and even countries. Indeed, we find that, …
-
Efficient Cohesive Subgraph Computation in Temporal Graphs
… over time. Among various cohesion models, the k-core has emerged as a simple yet powerful abstraction, and its extension to temporal settings has attracted increasing attention in recent years. This thesis investigates the problem of cohesive subgraph computation and search in temporal graphs, …
-
Core Structures in Random Graphs and Hypergraphs
The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random …
-
Assessing The Resilience Of Mycorrhizal Networks Following Central Tree Removal
… By applying centrality analysis and performing k-core partitioning on these networks, we are able to identify the trees that are most important and central to a MN and observe the effects of removing these trees. We also perform random partitioning on these networks and compare the results to the …
-
Efficient algorithms for discovering importance-based communities in large web-scale networks
k-core is a notion capturing the cohesiveness of a subgraph in a social network graph. Most of the current research work only consider pure network graphs and neglect an important property of the nodes: influence. Li, Qin, Yu, and Mao introduced a novel community model called k-influential …
-
Computing (1+ϵ)-Approximate Degeneracy in Sublinear Time
… degeneracy of a graph is a subproblem of the k-core decomposition problem. In this paper, we present a (1 + ϵ)-approximate solution to the degeneracy problem which runs in O(n log n) time on a graph with n nodes, sublinear in the input size for dense graphs, by sampling a small number of …
-
Clique Relaxations & the Minority Districting Problem
… and computational experiments. The Anchored k-core Problem is a variant of the maximum k-core problem, which itself is a relaxation of a clique. We propose an integer programming formulation for the anchored k-core problem, define and study the polyhedra of the maximum anchored k-core problem, …
-
Clique Generalizations and Related Problems
… generalization problems: co-2-plexes and k-cores. A k-core is a subgraph with minimum degree greater than or equal to k. In this work, I discuss the minimal k-core problem and the minimum k-core problem. I present a backtracking algorithm to find all minimal k-cores of a given undirected …
-
A distributed, compact routing protocol for the Internet
… compact protocol for Cowen routing, using the k-core graph decomposition. Previous compact routing work showed the k-core graph decomposition is useful for Cowen Routing on the Internet, but no distributed form existed. This dissertation gives a distributed k-core algorithm optimised to be …
-
Distributed graph decomposition algorithms on Apache Spark
… Two such very popular decompositions, k-core and k-truss of a graph give very useful insight about the graph vertex and edges respectively. These decompositions have been applied to solve protein functions reasoning on protein-protein networks, fraud detection and missing link prediction …
-
Cohesive Structure Based Network Analysis: From Motif Level to Subgraph Level
… cohesive subgraph model named radius-bounded k-core (RB-k- core) to capture cohesive subgraphs that satisfy both social and spatial constraints on geo-social networks. We use k- core to ensure the social cohesiveness and we use a radius-bounded circle to restrict the locations of users in an …
-
O papel de sítios periféricos no processo epidêmico SIS
… como investigado por meio da decomposição k-core em redes com distribuição em lei de potência com γ < 52 . No entanto, há uma desproporcional falta de estudos sistemáticos no esforço de discriminar os impactos de sítios periféricos na dinâmica do modelo SIS. Dentre os efeitos esperados, …
-
Cohesive subgraph computation over large heterogeneous information networks
… Typical cohesive subgraph models include k-core, k-truss, k-ECC, maximal-clique, quasi-clique, etc. Among the cohesive subgraph models, the k-core and the k-truss have been demonstrated to be outstanding, as they can achieve both high cohesiveness and high computational efficiency. …
-
Percolation and reinforcement on complex networks
… context of both traditional percolation and k-core percolation—the resilience of complex networks with tunable degree distributions or directed dependency links under random, localized or targeted attacks; ii) develop and propose a reinforcement scheme to eradicate catastrophic collapses that …
-
Coloring and degeneracy for determining very large and sparse derivative matrices
… We have introduced degeneracy and maximum k-core for sparse matrices to solve the problem in stages. Our combined approach produce better results in terms of partitioning than DSJM and for some test instances, we report optimal partitioning for the first time.
Page 1 of 3