Source author record

Katarzyna Rybarczyk

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Social and Information Networks

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Modularity of preferential attachment graphs

We study the preferential attachment model $G_n^h$ . A graph $G_n^h$ is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to $h\ge 1$ already existing vertices, and these are chosen with probability proportional to their current degrees. We are particularly interested in the community structure of $G_n^h$ , which is expressed in terms of the so-called modularity. We prove that the modularity of $G_n^h$ is with high probability upper bounded by a function that tends to $0$ as $h$ tends to infinity. This resolves the conjecture of Prokhorenkova, Pralat, and Raigorodskii from 2016. As a byproduct, we obtain novel concentration results (which are interesting in their own right) for the volume and edge density parameters of vertex subsets of $G_n^h$ . The key ingredient here is the definition of the function $μ$ , which serves as a natural measure for vertex subsets, and is proportional to the average size of their volumes. This extends previous results on the topic by Frieze, Pralat, Pérez-Giménez, and Reiniger from 2019.

preprint2026arXiv

Note on edge expansion and modularity in preferential attachment graphs

Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and is an important notion in theoretical computer science. Modularity is a measure of how well a graph can be partitioned into communities and is widely used in clustering applications. We study these two parameters in two commonly considered models of random preferential attachment graphs, with $h \geq 2$ edges added per step. We establish new bounds for the likely edge expansion for both random models. Using bounds for edge expansion of small subsets of vertices, we derive new upper bounds also for the modularity values for small $h$ .

preprint2020arXiv

The cover time of a sparse random intersection graph

Many known networks have structure of affiliation networks, where each of $n$ network's nodes (actors) selects an attribute set from a given collection of $m$ attributes and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study behaviour of the random walk on such networks. For that purpose we use commonly used model of such networks -- random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph ${\cal G}(n,m,p)$ at the connectivity threshold and above it. We consider the range of $n,m,p$ where the typical attribute is shared by (stochastically) bounded number of actors.

preprint2016arXiv

Poisson approximation of counts of subgraphs in random intersection graphs

Random intersection graphs are characterized by three parameters: $n$ , $m$ and $p$ , where $n$ is the number of vertices, $m$ is the number of objects, and $p$ is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When $m=\lfloor n^α\rfloor$ for constant $α$ , we provide a condition, called {\em strictly $α$ -balanced}, for the Poisson convergence of the number of induced copies of a fixed subgraph.

preprint2015arXiv

Equivalence of the random intersection graph and G(n,p)

We solve the conjecture posed by Fill, Scheinerman and Singer-Cohen and show the equivalence of the sharp threshold functions of the random intersection graph G(n,m,p) with $m >= n^3$ and a graph in which each edge appears independently. Moreover we prove sharper equivalence results under some additional assumptions.

preprint2009arXiv

Sharp threshold functions for the random intersection graph via coupling method?

We will present a new method, which enables us to find threshold functions for many properties in random intersection graphs. This method will be used to establish sharp threshold functions in random intersection graphs for k-connectivity, perfect matching containment and Hamilton cycle containment.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.