Search

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 community detection algorithms that are unsupervised by nature. We propose ABCDe, a multi-threaded implementation of the ABCD (Artificial Benchmark for Community Detection) graph generator. We discuss the implementation details of the algorithm and compare it with both the previously available sequential version of the ABCD model and with the parallel implementation of the standard and extensively used LFR (Lancichinetti--Fortunato--Radicchi) generator. We show that ABCDe is more than ten times faster and scales better than the parallel implementation of LFR provided in NetworKit. Moreover, the algorithm is not only faster but random graphs generated by ABCD have similar properties to the ones generated by the original LFR algorithm, while the parallelized NetworKit implementation of LFR produces graphs that have noticeably different characteristics., 15 pages, 10 figures, 1 table

Users on social networks such as Twitter interact with and are influenced by each other without much knowledge of the identity behind each user. This anonymity has created a perfect environment for bot and hostile accounts to influence the network by mimicking real-user behaviour. To combat this, research into designing algorithms and datasets for identifying bot users has gained significant attention. In this work, we highlight various techniques for classifying bots, focusing on the use of node and structural embedding algorithms. We show that embeddings can be used as unsupervised techniques for building features with predictive power for identifying bots. By comparing features extracted from embeddings to other techniques such as NLP, user profile and node-features, we demonstrate that embeddings can be used as unique source of predictive information. Finally, we study the stability of features extracted using embeddings for tasks such as bot classification by artificially introducing noise in the network. Degradation of classification accuracy is comparable to models trained on carefully designed node features, hinting at the stability of embeddings.

Zero forcing is a deterministic iterative graph colouring process in which vertices are coloured either blue or white, and in every round, any blue vertices that have a single white neighbour force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbour to become blue. We explore the propagation time for probabilistic zero forcing on hypercubes and grids.

Graph embedding is a transformation of nodes of a network into a set of vectors. A good embedding should capture the underlying graph topology and structure, node-to-node relationship, and other relevant information about the graph, its subgraphs, and nodes themselves. If these objectives are achieved, an embedding is a meaningful, understandable, and often compressed representation of a network. Unfortunately, selecting the best embedding is a challenging task and very often requires domain experts. In this paper, we extend the framework for evaluating graph embeddings that was recently introduced by the authors. Now, the framework assigns two scores, local and global, to each embedding that measure the quality of an evaluated embedding for tasks that require good representation of local and, respectively, global properties of the network. The best embedding, if needed, can be selected in an unsupervised way, or the framework can identify a few embeddings that are worth further investigation. The framework is flexible, scalable, and can deal with undirected/directed, weighted/unweighted graphs., 32 pages, 15 figures

Let T be a random tree taken uniformly at random from the family of labelled trees on n vertices. In this note, we provide bounds for c ( n ) , the number of sub-trees of T that hold asymptotically almost surely (a.a.s.). With computer support we show that a.a.s. 1 . 4180538 6 n ≤ c ( n ) ≤ 1 . 4195988 1 n . Moreover, there is a strong indication that, in fact, a.a.s. c ( n ) ≤ 1 . 4180618 3 n .

We consider schedules of unit-duration tasks with random dependencies. Formally the schedules are obtained by imposing a random partial order of vertices in an Erdős-Renyi graph. For such schedules, we provide asymptotic formulas for the parallel execution time and for the required number of processors in a greedy allocation scheme as a function of connection probability. We also derive asymptotic bounds for the number of required processors in an optimal allocation scheme. We test our results for small schedule sizes using simulation and conclude that the convergence to asymptotic results is achieved relatively fast in practice. In our simulation experiment, we define and compare the efficiency of Mixed Integer Programming and Constraint Programming approaches to find the exact solution of the optimal allocation scheme and conclude that Constraint Programming is more efficient in our setting. In the last part of the paper, we provide preliminary results of similar analysis for random schedules generated from arbitrary graphs.

Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge-connected graph has an edge orientation in which every out-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge connected 5-regular graphs.

A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge-probabilities p=p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function., 25 pages

Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

International audience; Graph burning is a deterministic discrete time graph process that can be interpreted as a model for the spread of influence in social networks. The burning number of a graph is the minimum number of steps in a graph burning process for that graph. In this paper, we consider the burning number of graph products. We find some general bounds on the burning number of the Cartesian product and the strong product of graphs. In particular, we determine the asymptotic value of the burning number of hypercube graphs and we present a conjecture for its exact value. We also find the asymptotic value of the burning number of the strong grids, and using that we obtain a lower bound on the burning number of the strong product of graphs in terms of their diameters. Finally, we consider the burning number of the lexicographic product of graphs and we find a characterization for that.

We study a primitive vehicle routing-type problem in which a fleet of n unit speed robots start from a point within a non-obtuse triangle \(\Delta \), where \(n \in \{1,2,3\}\). The goal is to design robots’ trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing \(\Delta \) into regions with respect to the type of optimal trajectory that each point P admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan \(R_n(P)\) is determined, for \(n\in \{1,2,3\}\). These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define \(\mathscr {R}_{n,m} (\Delta )= \max _{P \in \Delta } R_n(P)/R_m(P)\), and we prove that, over all non-obtuse triangles \(\Delta \): (i) \(\mathscr {R}_{1,3}(\Delta )\) ranges from \(\sqrt{10}\) to 4, (ii) \(\mathscr {R}_{2,3}(\Delta )\) ranges from \(\sqrt{2}\) to 2, and (iii) \(\mathscr {R}_{1,2}(\Delta )\) ranges from 5/2 to 3. In every case, we pinpoint the starting points within every triangle \(\Delta \) that maximize \(\mathscr {R}_{n,m} (\Delta )\), as well as we identify the triangles that determine all \(\inf _\Delta \mathscr {R}_{n,m}(\Delta )\) and \(\sup _\Delta \mathscr {R}_{n,m}(\Delta )\) over the set of non-obtuse triangles.

We propose a community detection algorithm for hypergraphs. The main feature of this algorithm is that it can be adjusted to various scenarios depending on how often vertices in one community share hyperedges with vertices from other community.

The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v , and adds the edge u v to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c ∗ n rounds, where the value of c ∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c ∗ 2 . 61135 . This improves upon the previously best known upper bound of 3 n rounds. We also show that the previously best lower bound of ( ln 2 + ln ( 1 + ln 2 ) + o ( 1 ) ) n is not tight.

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$. The unit acquisition number of $G$, denoted by $a_u(G)$, is the minimum cardinality of the set of vertices with positive weight at the end of the process (over all acquisition protocols). In this paper, we investigate the Erdős-Rényi random graph process $(\mathcal{G}(n,m))_{m =0}^{N}$, where $N = {n \choose 2}$. We show that asymptotically almost surely $a_u(\mathcal{G}(n,m)) = 1$ right at the time step the random graph process creates a connected graph. Since trivially $a_u(\mathcal{G}(n,m)) \ge 2$ if the graphs is disconnected, the result holds in the strongest possible sense.

Consider the following broadcasting process run on a connected graph G = ( V , E ) . Suppose that k ≥ 2 agents start on vertices selected from V uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on G , with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time ξ ( G , k ) is the time it takes to spread the message to all agents. Our ultimate goal is to gain a better understanding of the broadcasting process run on real-world networks of roads of large cities that might shed some light on the behaviour of future autonomous and connected vehicles. Due to the complexity of road networks, such phenomena have to be studied using simulation in practical applications. In this paper, we study the process on the simplest scenario, i.e., the family of complete graphs, as in this case the problem is analytically tractable. We provide tight bounds for ξ ( K n , k ) that hold asymptotically almost surely for the whole range of the parameter k . These theoretical results reveal interesting relationships and, at the same time, are also helpful to understand and explain the behaviour we observe in more realistic networks.

Real-world complex networks are usually being modeled as graphs. The concept of graphs assumes that the relations within the network are binary (for instance, between pairs of nodes); however, this is not always true for many real-life scenarios, such as peer-to-peer communication schemes, paper co-authorship, or social network interactions. For such scenarios, it is often the case that the underlying network is better and more naturally modeled by hypergraphs. A hypergraph is a generalization of a graph in which a single (hyper)edge can connect any number of vertices. Hypergraphs allow modelers to have a complete representation of multi-relational (many-to-many) networks; hence, they are extremely suitable for analyzing and discovering more subtle dependencies in such data structures. Working with hypergraphs requires new software libraries that make it possible to perform operations on them, from basic algorithms (such as searching or traversing the network) to computing significant hypergraph measures, to including more challenging algorithms (such as community detection). In this paper, we present a new software library, SimpleHypergraphs.jl, written in the Julia language and designed for high-performance computing on hypergraphs and propose two new algorithms for analyzing their properties: s-betweenness and modified label propagation. We also present various approaches for hypergraph visualization integrated into our tool. In order to demonstrate how to exploit the library in practice, we discuss two case studies based on the 2019 Yelp Challenge dataset and the collaboration network built upon the Game of Thrones TV series. The results are promising and they confirm the ability of hypergraphs to provide more insight than standard graph-based approaches., 32 pages, 10 figures, 7 tables, submitted to Internet Mathematics Journal

Most of the current complex networks that are of interest to practitioners possess a certain community structure that plays an important role in understanding the properties of these networks. Moreover, many machine learning algorithms and tools that are developed for complex networks try to take advantage of the existence of communities to improve their performance or speed. As a result, there are many competing algorithms for detecting communities in large networks. Unfortunately, these algorithms are often quite sensitive and so they cannot be fine-tuned for a given, but a constantly changing, real-world network at hand. It is therefore important to test these algorithms for various scenarios that can only be done using synthetic graphs that have built-in community structure, power-law degree distribution, and other typical properties observed in complex networks. The standard and extensively used method for generating artificial networks is the LFR graph generator. Unfortunately, this model has some scalability limitations and it is challenging to analyze it theoretically. Finally, the mixing parameter $\mu$, the main parameter of the model guiding the strength of the communities, has a non-obvious interpretation and so can lead to unnaturally-defined networks. In this paper, we provide an alternative random graph model with community structure and power-law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD). We show that the new model solves the three issues identified above and more. The conclusion is that these models produce comparable graphs but ABCD is fast, simple, and can be easily tuned to allow the user to make a smooth transition between the two extremes: pure (independent) communities and random graph with no community structure., Comment: 22 pages, 4 figures

Consider the following broadcasting process run on a connected graph $G=(V,E)$. Suppose that $k \ge 2$ agents start on vertices selected from $V$ uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on $G$, with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time $\xi(G,k)$ is the time it takes to spread the message to all agents. We provide tight bounds for $\xi(P_n,k)$ and $\xi(C_n,k)$ that hold asymptotically almost surely for the whole range of the parameter~$k$., Comment: arXiv admin note: text overlap with arXiv:2003.08501

The invention and implementation of smart connected cars will change the way how the transportation networks in cities around the world operate. This technological shift will not happen instantaneously—for many years, both human-driven and smart connected vehicles will coexist. In this paper, using a multiagent simulation framework, we model a complex urban transportation system that involves heterogeneous participants. Vehicles are assigned into two groups: the first one consists of smart cars and the second one involves regular ones. Vehicles in the former group are capable of rerouting in response to changes in the observed traffic while regular ones rely on historical information only. The goal of the paper is to analyze the effect of changing smart cars penetration on system characteristics, in particular, the total travelling time. The smart car routing algorithm proposed in this paper reduced travelling time up to 30%. Analysis has shown that the behaviour of the system and optimal configuration of underlying algorithms change dynamically with smart vehicles penetration level.