Source author record

Mohammed Amin Abdullah

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

ResearcherUnclaimed source record

math.PR Information Theory math.CO math.IT

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Robust On-line Matrix Completion on Graphs

We study online robust matrix completion on graphs. At each iteration a vector with some entries missing is revealed and our goal is to reconstruct it by identifying the underlying low-dimensional subspace from which the vectors are drawn. We assume there is an underlying graph structure to the data, that is, the components of each vector correspond to nodes of a certain (known) graph, and their values are related accordingly. We give algorithms that exploit the graph to reconstruct the incomplete data, even in the presence of outlier noise. The theoretical properties of the algorithms are studied and numerical experiments using both synthetic and real world datasets verify the improved performance of the proposed technique compared to other state of the art algorithms.

preprint2015arXiv

Local majority dynamics on preferential attachment graphs

Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. At each time step, each vertex $v$ in $G$ polls $k$ random neighbours and takes the majority colour. If it doesn't have $k$ neighbours, it simply polls all of them, or all less one if the degree of $v$ is even. We study this protocol on the preferential attachment model of Albert and Barabási, which gives rise to a degree distribution that has roughly power-law $P(x) \sim \frac{1}{x^{3}}$ , as well as generalisations which give exponents larger than $3$ . The setting is as follows: Initially each vertex of $G$ is red independently with probability $α< \frac{1}{2}$ , and is otherwise blue. We show that if $α$ is sufficiently biased away from $\frac{1}{2}$ , then with high probability, consensus is reached on the initial global majority within $O(\log_d \log_d t)$ steps. Here $t$ is the number of vertices and $d \geq 5$ is the minimum of $k$ and $m$ (or $m-1$ if $m$ is even), $m$ being the number of edges each new vertex adds in the preferential attachment generative process. Additionally, our analysis reduces the required bias of $α$ for graphs of a given degree sequence studied by the first author (which includes, e.g., random regular graphs).

preprint2014arXiv

A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$ , where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$ , complete infection occurs with high probability as $t \rightarrow \infty$ , but when $a(t) \ll a_c (t)$ , then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$ .

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.