Networks are widely used to model a variety of complex, often multi-disciplinary, systems in which the relationships between their sub-parts play a significant role. In particular, there is extensive research on the topological properties associated with their structure as this allows the analysis of the overall behaviour of such networks. However, extracting networks from structured and unstructured data sets raises several challenges, including addressing any inconsistency present in the data, as well as the difficulty in investigating their properties especially when the topological structure is not fully determined or not explicitly defined. In this paper, we propose a novel method to address the automated identification, assessment and ranking of the most likely structure associated with networks extracted from a variety of data sets. More specifically, our approach allows to mine data to assess whether their associated networks exhibit properties comparable to well-known structures, namely scale-free, small world and random networks. The main motivation is to provide a toolbox to classify and analyse real-world networks otherwise difficult to fully assess due to their potential lack of structure. This can be used to investigate their dynamical and statistical behaviour which would potentially lead to a better understanding and prediction of the properties of the system (s) they model. Our initial validation shows the potential of our method providing relevant and accurate results.

An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal is to find an assignment of values to the variables that minimizes the sum. We study (assuming that ${PTIME}\neq{NP}$) how the complexity of this very general problem depends on the functions allowed in the instances. The case when the variables can take only two values was classified by Cohen et al.: essentially, submodular functions give rise to the only tractable case, and any non--submodular function can be used to express, in a certain specific sense, the NP-hard Max Cut problem. We investigate the case when the variables can take three values. We identify a new infinite family of conditions that includes bisubmodularity as a special case and which can collectively be called skew bisubmodularity. By a recent result of Thapper and Živný, this condition implies that the corresponding VCSP can be solved by linear programming. We prove that submodularity, with respect to a total order, and skew bisubmodularity give rise to the only tractable cases, and, in all other cases, again, Max Cut can be expressed. We also show that our characterization of tractable cases is tight; that is, none of the conditions can be omitted.

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use this extension to show that skew bisubmodular functions given by an oracle can be minimized in polynomial time.

An instance of the (finite-)Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, each function depending on a subset of the variables. The goal is to find an assignment of values to the variables that minimises the sum. We study (assuming that PTIME ≠ NP) how the complexity of this very general problem depends on the functions allowed in the instances. The case when the variables can take only two values was classified by Cohen et al.: essentially, submodular functions give rise to the only tractable case, and any non-submodular function can be used to express, in a certain specific sense, the NP-hard Max Cut problem. We investigate the case when the variables can take three values. We identify a new infinite family of conditions that includes bisubmodularity as a special case and which can collectively be called skew bisubmodularity. By a recent result of Thapper and Živný, this condition implies that the corresponding VCSP can be solved by linear programming. We prove that submodularity with respect to a total order and skew bisubmodularity give rise to the only tractable cases, and, in all other cases, again, Max Cut can be expressed. We also show that our characterisation of tractable cases is tight, that is, none of the conditions can be omitted. Thus, our results provide a new dichotomy theorem in constraint satisfaction research, and lead to a whole series of intriguing open problems in submodularity research.

Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q that is, it fails to do so with probability 1-q. The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, with q = 1 is very well understood. In particular, Frieze and Grimmett proved that with probability 1-o(1) the push protocol completes the broadcasting of the message within (1 ± ¿) (log2n + ln n) stages, where n is the number of nodes in the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. In this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. We show that if p ¿ ¿(n)ln n/n, where ¿(n) is any function that tends to infinity as n grows, then the push protocol with faulty transmissions broadcasts the message within (1± ¿) (log1+qn + 1/q ln n) stages with probability 1-o(1). In other words, in almost every network of density d such that d ¿ ¿(n) ln n, the push protocol broadcasts a message as fast as in a fully connected network and the speed is only affected by the success probability q. This is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing. Our results are accompanied by experimental evaluation.

In this paper, we provide a detailed comparison between a fully randomized protocol for rumor spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich, and Sauerwald [Quasirandom rumor spreading, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 773–781]. In the former, initially there is one vertex which holds a piece of information, and during each round every one of the informed vertices chooses uniformly at random and independently one of its neighbors and informs it. In the quasirandom version of this method (cf. Doerr, Friedrich, and Sauerwald) each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor, and at each subsequent round it picks the next neighbor from its list and informs it. We give a precise analysis of the evolution of the quasirandom protocol on the complete graph with n vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if $S(n)$ denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function $\omega(n)$, we have $\log_2 n + \ln n - 4 \ln \ln n \leq S(n) \leq \log_2 n + \ln n + \omega(n)$, with probability $1-o(1)$.