Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe idemetric property: when most distances are (almost) the same
83
0
0.0
(
0
)
Added by
Andrew Lewis-Pye
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce the emph{idemetric} property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We then consider how satisfaction of the idemetric property is relevant to algorithm design. For idemetric graphs we observe, for example, that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. Since we are able to show that Kleinbergs model is idemetric, these results contrast nicely with the well known negative results of Kleinberg concerning efficient decentralised algorithms for finding short paths: for precisely the same model as Kleinbergs negative results hold, we are able to show that very efficient (and decentralised) algorithms exist if one allows for reasonable preprocessing. For deterministic distributed routing algorithms we are also able to obtain results proving that less routing information is required for idemetric graphs than the worst case in order to achieve stretch less than 3 with high probability: while $Omega(n^2)$ routing information is required in the worst case for stretch strictly less than 3 on almost all pairs, for idemetric graphs the total routing information required is $O(nlog(n))$.
rate research
Read More
People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
Far-right actors are often purveyors of Islamophobic hate speech online, using social media to spread divisive and prejudiced messages which can stir up intergroup tensions and conflict. Hateful content can inflict harm on targeted victims, create a sense of fear amongst communities and stir up intergroup tensions and conflict. Accordingly, there is a pressing need to better understand at a granular level how Islamophobia manifests online and who produces it. We investigate the dynamics of Islamophobia amongst followers of a prominent UK far right political party on Twitter, the British National Party. Analysing a new data set of five million tweets, collected over a period of one year, using a machine learning classifier and latent Markov modelling, we identify seven types of Islamophobic far right actors, capturing qualitative, quantitative and temporal differences in their behaviour. Notably, we show that a small number of users are responsible for most of the Islamophobia that we observe. We then discuss the policy implications of this typology in the context of social media regulation.
Graph comparison is a fundamental operation in data mining and information retrieval. Due to the combinatorial nature of graphs, it is hard to balance the expressiveness of the similarity measure and its scalability. Spectral analysis provides quintessential tools for studying the multi-scale structure of graphs and is a well-suited foundation for reasoning about differences between graphs. However, computing full spectrum of large graphs is computationally prohibitive; thus, spectral graph comparison methods often rely on rough approximation techniques with weak error guarantees. In this work, we propose SLaQ, an efficient and effective approximation technique for computing spectral distances between graphs with billions of nodes and edges. We derive the corresponding error bounds and demonstrate that accurate computation is possible in time linear in the number of graph edges. In a thorough experimental evaluation, we show that SLaQ outperforms existing methods, oftentimes by several orders of magnitude in approximation accuracy, and maintains comparable performance, allowing to compare million-scale graphs in a matter of minutes on a single machine.
Working within the framework of free actions of countable amenable groups on compact metrizable spaces, we show that the small boundary property is equivalent to a density version of almost finiteness, which we call almost finiteness in measure, and that under this hypothesis the properties of almost finiteness, comparison, and $m$-comparison for some nonnegative integer $m$ are all equivalent. The proof combines an Ornstein-Weiss tiling argument with the use of zero-dimensional extensions which are measure-isomorphic over singleton fibres. These kinds of extensions are also employed to show that if every free action of a given group on a zero-dimensional space is almost finite then so are all free actions of the group on spaces with finite covering dimension. Combined with recent results of Downarowicz-Zhang and Conley-Jackson-Marks-Seward-Tucker-Drob on dynamical tilings and of Castillejos-Evington-Tikuisis-White-Winter on the Toms-Winter conjecture, this implies that crossed product C$^*$-algebras arising from free minimal actions of groups with local subexponential growth on finite-dimensional spaces are classifiable in the sense of Elliotts program. We show furthermore that, for free actions of countably infinite amenable groups, the small boundary property implies that the crossed product has uniform property $Gamma$, which under minimality confirms the Toms-Winter conjecture for such crossed products by the aforementioned work of Castillejos-Evington-Tikuisis-White-Winter.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
