Gap properties in random intersection graphs
Loading...
Date
2024-03-27
Authors
Καρέλας, Γεώργιος-Νικόλαος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Networks, which mathematically can be modeled using graphs, are widely used during the last years to represent systems with entities (nodes) that interact with each other (edges). Thanks to their structure, networks can be applied in many different settings and that is why we can find applications of them in many fields of science, such as biology, economics, chemistry, social sciences and computer science. One of the most important open problems in the study of graphs is that of finding, in an arbitrary graph, its maximum clique, that is a subset of its vertices which are all connected to each other. The problem of finding a clique can be translated, in the case of social networks, to a community detection problem. Here, we focus on random graphs, which were initially considered in order to study the properties of "typical" graphs. Specifically, we focus on the random intersection graph model which consists of two parts; an attribute set (labels) and all the graphs whose nodes choose each one of the attributes (labels) independently and equiprobably. Two nodes, in a graph of this model, are connected if they have at least one label in common. This creates a dependency between the edges, making this model an accurate representation of social networks. The goal of this thesis is to study dense random intersection graphs and try to capture the difficulty of detecting a maximum clique in this setting. We give an extended review on random intersection graphs, providing some basic structural results on the model. In addition, we present some related work to the maximum clique problem and include the notion of average-case hardness for the maximum clique problem in our setting defined by [35]. Our work leads to the conjecture that finding a maximum clique using the adjacency matrix of the graph requires superpolynomial time. Furthermore, we use a result by [20] which helps us get our second conjecture on the generalization of the Single Label Clique theorem [36].
Description
Keywords
Random graphs, Random intersection graphs, Gap properties, Maximum clique, Overlap gap property