83 citations · 346 across the 78 of their papers we have counts for
106 papers
Hopping Forcing Number in Random -regular Graphs
Pawel Pralat, Harjas Singh
Hopping forcing is a single player combinatorial game in which the player is presented a graph on vertices, some of which are initially blue with the remaining vertices being w…
Creating Subgraphs in Semi-Random Hypergraph Games
Natalie Behague, Pawel Pralat, Andrzej Rucinski
The semi-random hypergraph process is a natural generalisation of the semi-random graph process, which can be thought of as a one player game. For fixed , starting with an e…
Modularity Based Community Detection in Hypergraphs
Bogumił Kamiński, Paweł Misiorek, Paweł Prałat +1
In this paper, we propose a scalable community detection algorithm using hypergraph modularity function, h-Louvain. It is an adaptation of the classical Louvain algorithm in the co…
Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
Michael Molloy, Pawel Pralat, Gregory B. Sorkin
We study the 2-offer semirandom 3-uniform hypergraph model on vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creati…
Self-similarity of Communities of the ABCD Model
Jordan Barrett, Bogumil Kaminski, Pawel Pralat +1
The Artificial Benchmark for Community Detection (ABCD) graph is a random graph model with community structure and power-law distribution for both degrees and community sizes. The…
Linear Colouring of Binomial Random Graphs
Austin Eide, Paweł Prałat
We investigate the linear chromatic number of the binomial random graph on vertices in which each edge appears independently with probability…
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than Rounds
Alan Frieze, Pu Gao, Calum MacRury +2
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on vertices. In each round, a vertex is…
Predicting Properties of Nodes via Community-Aware Features
Bogumił Kamiński, Paweł Prałat, François Théberge +1
This paper shows how information about the network's community structure can be used to define node features with high predictive power for classification tasks. To do so, we defin…
Asynchronous Majority Dynamics on Binomial Random Graphs
Divyarthi Mohan, Pawel Pralat
We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is "corr…
The Fagnano Triangle Patrolling Problem
Konstantinos Georgiou, Somnath Kundu, Pawel Pralat
We investigate a combinatorial optimization problem that involves patrolling the edges of an acute triangle using a unit-speed agent. The goal is to minimize the maximum (1-gap) id…
Unsupervised Framework for Evaluating and Explaining Structural Node Embeddings of Graphs
Ashkan Dehghan, Kinga Siuta, Agata Skorupka +4
An embedding is a mapping from a set of nodes of a network into a real vector space. Embeddings can have various aims like capturing the underlying graph topology and structure, no…
Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
David Gamarnik, Mihyun Kang, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Power of Choices in the Semi-Random Graph Process
Paweł Prałat, Harjas Singh
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Label propagation on binomial random graphs
Marcos Kiwi, Lyuben Lichev, Dieter Mitsche +1
We study the behavior of a label propagation algorithm (LPA) on the Erdős-Rényi random graph . Initially, given a network, each vertex starts with a random label…
Artificial Benchmark for Community Detection with Outliers (ABCD+o)
Bogumił Kamiński, Paweł Prałat, François Théberge
The Artificial Benchmark for Community Detection graph (ABCD) is a random graph model with community structure and power-law distribution for both degrees and community sizes. The…
Hypergraph Artificial Benchmark for Community Detection (h-ABCD)
Bogumił Kamiński, Paweł Prałat, François Théberge
The Artificial Benchmark for Community Detection (ABCD) graph is a recently introduced random graph model with community structure and power-law distribution for both degrees and c…
Almost all 9-regular graphs have a modulo-5 orientation
Michelle Delcourt, Reaz Huq, Pawel Pralat
In 1972 Tutte famously conjectured that every 4-edge-connected graph has a nowhere zero 3-flow; this is known to be equivalent to every 5-regular, 4-edge-connected graph having an…
Rainbow spanning trees in randomly coloured
Deepak Bal, Alan Frieze, Pawel Pralat
Given a graph on vertices and an assignment of colours to its edges, a set of edges is said to be rainbow if edges from have pairwise different co…
The Erdős-Gyárfás function -- so Gyárfás was right
Patrick Bennett, Ryan Cushman, Andrzej Dudek +1
A -coloring of is an edge-coloring of where every -clique spans at least five colors. We show that there exist -colorings of using $\frac 56 n…
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process
Pu Gao, Calum MacRury, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Modularity of the ABCD Random Graph Model with Community Structure
Bogumil Kaminski, Bartosz Pankratz, Pawel Pralat +1
The Artificial Benchmark for Community Detection (ABCD) graph is a random graph model with community structure and power-law distribution for both degrees and community sizes. The…
Properties and Performance of the ABCDe Random Graph Model with Community Structure
Bogumił Kamiński, Tomasz Olczak, Bartosz Pankratz +2
In this paper, we investigate properties and performance of synthetic random graph models with a built-in community structure. Such models are important for evaluating and tuning c…
Edge and Pair Queries -- Random Graphs and Complexity
Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat
We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random gr…
Survey of Generative Methods for Social Media Analysis
Stan Matwin, Aristides Milios, Paweł Prałat +2
This survey draws a broad-stroke, panoramic picture of the State of the Art (SoTA) of the research in generative methods for the analysis of social media data. It fills a void, as…