Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks
verfasst von : Ulrik Brandes, Eugenia Holm, Andreas Karrenbauer
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The existence of a densely knit core surrounded by a loosely connected periphery is a common macro-structural feature of social networks. Formally, the CorePeriphery problem is to partition the nodes of an undirected graph \(G=(V,E)\) such that a subset \(X\subset V\), the core, induces a dense subgraph, and its complement \(V\!\setminus \!X\), the periphery, induces a sparse subgraph. Split graphs represent the ideal case in which the core induces a clique and the periphery forms an independent set. The number of missing and superfluous edges in the core and the periphery, respectively, can be minimized in linear time via edit distance to the closest split graph.
We show that the CorePeriphery becomes intractable for standard notions of density other than the absolute number of misclassified pairs. Our main tool is a regularization procedure that transforms a given graph with maximum degree d into a d-regular graph with the same clique number by adding at most \(d\cdot n\) new nodes. This is of independent interest because it implies that finding a maximum clique in a regular graph is NP-hard to approximate to within a factor of \(n^{1/2-\varepsilon }\) for all \(\varepsilon >0\).