Publications related to Clustering coefficient

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Unsupervised Graph Representation Learning with Cluster-aware Self-training and Refining

Yichen Xu, Qiang Liu, Feng Yu

Unsupervised graph representation learning aims to learn low-dimensional node embeddings without supervision while preserving graph topological structures and node attributive features. Previous Graph Neural Networks (GNN) require a large number of labeled ...

Assoc Computing Machinery2023

Incompleteness of graph neural networks for points clouds in three dimensions

Michele Ceriotti, Sergey Pozdnyakov

Graph neural networks (GNN) are very popular methods in machine learning and have been applied very successfully to the prediction of the properties of molecules and materials. First-order GNNs are well known to be incomplete, i.e. there exist graphs that ...

IOP Publishing Ltd2022

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Covariance matrices for variance-suppressed simulations

Cheng Zhao

Cosmological N-body simulations provide numerical predictions of the structure of the Universe against which to compare data from ongoing and future surveys, but the growing volume of the Universe mapped by surveys requires correspondingly lower statistica ...

OXFORD UNIV PRESS2022

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021

Testing for Equivalence of Network Distribution Using Subgraph Counts

Sofia Charlotta Olhede

We consider that a network is an observation, and a collection of observed networks forms a sample. In this setting, we provide methods to test whether all observations in a network sample are drawn from a specified model. We achieve this by deriving the j ...

AMER STATISTICAL ASSOC2020

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Stochastic Gradient Descent for Spectral Embedding with Implicit Orthogonality Constraint

Pascal Frossard, Mireille El Gheche, Giovanni Chierchia

In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to larg ...

IEEE2019

Decentralized clustering for node-variant graph filtering with graph diffusion LMS

Ali H. Sayed, Roula Nassif

In this work, we consider the problem of estimating the coefficients of linear shift-invariant FIR graph filters. We assume hybrid node-varying graph filters where the network is decomposed into clusters of nodes and, within each cluster, all nodes have th ...

IEEE2018

Robust and Efficient Data Clustering with Signal Processing on Graphs

Lionel Jérémie Martin

Data is pervasive in today's world and has actually been for quite some time. With the increasing volume of data to process, there is a need for faster and at least as accurate techniques than what we already have. In particular, the last decade recorded t ...

EPFL2018

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum

Dimitri Nestor Alice Van De Ville, Maria Giulia Preti, Robin Jonathan Demesmaeker

The study of complex systems greatly benefits from graph models and their analysis. In particular, the eigendecomposition of the graph Laplacian lets emerge properties of global organization from local interactions; e.g., the Fiedler vector has the smalles ...

IEEE Institute of Electrical and Electronics Engineers2017

On the Structure of Cortical Microcircuits Inferred from Small Sample Sizes

Rodrigo de Campos Perin

The structure in cortical microcircuits deviates from what would be expected in a purely random network, which has been seen as evidence of clustering. To address this issue, we sought to reproduce the nonrandom features of cortical circuits by considering ...

Soc Neuroscience2017

Alignment and Assembly : Inferring Networks from Noisy Observations

Lyudmila Yartseva

Over recent years, many large network datasets become available, giving rise to novel and valuable applications of data mining and machine learning techniques. These datasets include social networks, the structure of the Internet, and protein-interaction n ...

EPFL2017

Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks

Nikolaos Geroliminis, Mohammadreza Saeedmanesh

The problem of clustering in urban traffic networks has been mainly studied in static framework by considering traffic conditions at a given time. Nevertheless, it is important to underline that traffic is a strongly time-variant process and it needs to be ...

2017

On random subgraphs of Kneser and Schrijver graphs

Andrei Kupavskii

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic num ...

Academic Press Inc Elsevier Science2016

Decentralized voltage control of clustered active distribution network by means of energy storage systems

Mario Paolone, Sidi-Rachid Cherkaoui, Maryam Bahramipanah

The paper presents a network partitioning strategy for the optimal voltage control of Active Distribution Networks (ADNs) actuated by means of a limited number of Distributed Energy Storage Systems (DESSs). The proposed partitioning uses a linear programmi ...

Elsevier2016

Clustering of heterogeneous networks with directional flows based on “Snake” similarities

Nikolaos Geroliminis, Mohammadreza Saeedmanesh

Aggregated network level modeling and control of traffic in urban networks have recently gained a lot of interest due to unpredictability of travel behaviors and high complexity of physical modeling in microscopic level. Recent research has shown the exist ...

Elsevier2016

Clustered planarity testing revisited

Radoslav Fulek, Jan Kyncl, Igor Malinovic

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generali ...

2015