Connectivity measures for internet topologies on the level of autonomous systems

Classical measures of network connectivity are the number of disjoint paths between a pair of nodes and the size of a minimum cut. For standard graphs, these measures can be computed efficiently using network flow techniques. However, in the Internet on the level of autonomous systems (ASs), referred to as AS-level Internet, routing policies impose restrictions on the paths that traffic can take in the network. These restrictions can be captured by the valley-free path model, which assumes a special directed graph model in which edge types represent relationships between ASs. We consider the adaptation of the classical connectivity measures to the valley-free path model, where it is -hard to compute them. Our first main contribution consists of presenting algorithms for the computation of disjoint paths, and minimum cuts, in the valley-free path model. These algorithms are useful for ASs that want to evaluate different options for selecting upstream providers to improve the robustness of their connection to the Internet. Our second main contribution is an experimental evaluation of our algorithms on four types of directed graph models of the AS-level Internet produced by different inference algorithms. Most importantly, the evaluation shows that our algorithms are able to compute optimal solutions to instances of realistic size of the connectivity problems in the valley-free path model in reasonable time. Furthermore, our experimental results provide information about the characteristics of the directed graph models of the AS-level Internet produced by different inference algorithms. It turns out that (i) we can quantify the difference between the undirected AS-level topology and the directed graph models with respect to fundamental connectivity measures, and (ii) the different inference algorithms yield topologies that are similar with respect to connectivity and are different with respect to the types of paths that exist between pairs of ASs.

On the radius of centrality in evolving communication networks

In this article, we investigate how the choice of the attenuation factor in an extended version of Katz centrality influences the centrality of the nodes in evolving communication networks. For given snapshots of a network, observed over a period of time, recently developed communicability indices aim to identify the best broadcasters and listeners (receivers) in the network. Here we explore the attenuation factor constraint, in relation to the spectral radius (the largest eigenvalue) of the network at any point in time and its computation in the case of large networks. We compare three different communicability measures: standard, exponential, and relaxed (where the spectral radius bound on the attenuation factor is relaxed and the adjacency matrix is normalised, in order to maintain the convergence of the measure). Furthermore, using a vitality-based measure of both standard and relaxed communicability indices, we look at the ways of establishing the most important individuals for broadcasting and receiving of messages related to community bridging roles. We compare those measures with the scores produced by an iterative version of the PageRank algorithm and illustrate our findings with two examples of real-life evolving networks: the MIT reality mining data set, consisting of daily communications between 106 individuals over the period of one year, a UK Twitter mentions network, constructed from the direct \emph{tweets} between 12.4k individuals during one week, and a subset the Enron email data set.

On the Fucik spectrum of the Laplacian on a torus

We study the Fucik spectrum of the Laplacian on a two-dimensional torus T(2). Exploiting the invariance properties of the domain T(2) with respect to translations we obtain a good description of large parts of the spectrum. In particular, for each eigenvalue of the Laplacian we will find an explicit global curve in the Fucik spectrum which passes through this eigenvalue; these curves are ordered, and we will show that their asymptotic limits are positive. On the other hand, using a topological index based on the mentioned group invariance, we will obtain a variational characterization of global curves in the Fucik spectrum; also these curves emanate from the eigenvalues of the Laplacian, and we will show that they tend asymptotically to zero. Thus, we infer that the variational and the explicit curves cannot coincide globally, and that in fact many curve crossings must occur. We will give a bifurcation result which partially explains these phenomena. (C) 2008 Elsevier Inc. All rights reserved.

Semilinear elliptic problems near resonance with a nonprincipal eigenvalue

We consider the Dirichlet problem for the equation -Delta u = lambda u +/- (x, u) + h(x) in a bounded domain, where f has a sublinear growth and h is an element of L-2. We find suitable conditions on f and It in order to have at least two solutions for X near to an eigenvalue of -Delta. A typical example to which our results apply is when f (x, u) behaves at infinity like a(x)vertical bar u vertical bar(q-2)u, with M > a(x) > delta > 0, and I < q < 2. (C) 2007 Elsevier Inc. All rights reserved.

The degree of polydispersity in micellar dispersions: A sum rule approach

Statistical properties of a two-dimensional ideal dispersion of polydisperse micelles are derived by analyzing the convergence properties of a sum rule set by mass conservation. Internal micellar degrees of freedom are accounted for by a microscopic model describing small displacements of the constituting amphiphiles with respect to their equilibrium positions. The transfer matrix (TM) method is employed to compute internal micelle partition function. We show that the conditions under which the sum rule is saturated by the largest eigenvalue of the TM determine the value of amphiphile concentration above which the dispersion becomes highly polydisperse and micelle sizes approach a Schultz distribution. (C) 2011 Elsevier B.V. All rights reserved.

The stochastic nature of predator-prey cycles

We study by numerical simulations the time correlation function of a stochastic lattice model describing the dynamics of coexistence of two interacting biological species that present time cycles in the number of species individuals. Its asymptotic behavior is shown to decrease in time as a sinusoidal exponential function from which we extract the dominant eigenvalue of the evolution operator related to the stochastic dynamics showing that it is complex with the imaginary part being the frequency of the population cycles. The transition from the oscillatory to the nonoscillatory behavior occurs when the asymptotic behavior of the time correlation function becomes a pure exponential, that is, when the real part of the complex eigenvalue equals a real eigenvalue. We also show that the amplitude of the undamped oscillations increases with the square root of the area of the habitat as ordinary random fluctuations. (C) 2009 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Short-time behaviour of demand and price viewed through an exactly solvable model for heterogeneous interacting market agents

We introduce a stochastic heterogeneous interacting-agent model for the short-time non-equilibrium evolution of excess demand and price in a stylized asset market. We consider a combination of social interaction within peer groups and individually heterogeneous fundamentalist trading decisions which take into account the market price and the perceived fundamental value of the asset. The resulting excess demand is coupled to the market price. Rigorous analysis reveals that this feedback may lead to price oscillations, a single bounce, or monotonic price behaviour. The model is a rare example of an analytically tractable interacting-agent model which allows LIS to deduce in detail the origin of these different collective patterns. For a natural choice of initial distribution, the results are independent of the graph structure that models the peer network of agents whose decisions influence each other. (C) 2009 Elsevier B.V. All rights reserved.

The 3-colored Ramsey number of even cycles

Denote by R(L, L, L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdos conjectured that when L is the cycle C(n) on n vertices, R(C(n), C(n), C(n)) = 4n - 3 for every odd n > 3. Luczak proved that if n is odd, then R(C(n), C(n), C(n)) = 4n + o(n), as n -> infinity, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdos conjecture for all sufficiently large values of n. Figaj and Luczak determined an asymptotic result for the `complementary` case where the cycles are even: they showed that for even n, we have R(C(n), C(n), C(n)) = 2n + o(n), as n -> infinity. In this paper, we prove that there exists n I such that for every even n >= n(1), R(C(n), C(n), C(n)) = 2n. (C) 2009 Elsevier Inc. All rights reserved.

From the road network database to a graph for localization purposes

The problems of finding best facility locations require complete and accurate road network with the corresponding population data in a specific area. However the data obtained in road network databases usually do not fit in this usage. In this paper we propose our procedure of converting the road network database to a road graph which could be used in localization problems. The road network data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The population points are also processed in ordered to match with that graph. The reduction of the graph is done maintaining most of the accuracy for distance measures in the network.

A study on reliability in graph discovery

A critical question in data mining is that can we always trust what discovered by a data mining system unconditionally? The answer is obviously not. If not, when can we trust the discovery then? What are the factors that affect the reliability of the discovery? How do they affect the reliability of the discovery? These are some interesting questions to be investigated.

In this paper we will firstly provide a definition and the measurements of reliability, and analyse the factors that affect the reliability. We then examine the impact of model complexity, weak links, varying sample sizes and the ability of different learners to the reliability of graphical model discovery. The experimental results reveal that (1) the larger sample size for the discovery, the higher reliability we will get; (2) the stronger a graph link is, the easier the discovery will be and thus the higher the reliability it can achieve; (3) the complexity of a graph also plays an important role in the discovery. The higher the complexity of a graph is, the more difficult to induce the graph and the lower reliability it would be.

Graph matching with subdivision surfaces for texture synthesis on surfaces

Existing texture synthesis-from-example strategies for polygon meshes typically make use of three components: a multi-resolution mesh hierarchy that allows the overall nature of the pattern to be reproduced before filling in detail; a matching strategy that extends the synthesized texture using the best fit from a texture sample; and a transfer mechanism that copies the selected portion of the texture sample to the target surface. We introduce novel alternatives for each of these components. Use of p2-subdivision surfaces provides the mesh hierarchy and allows fine control over the surface complexity. Adaptive subdivision is used to create an even vertex distribution over the surface. Use of the graph defined by a surface region for matching, rather than a regular texture neighbourhood, provides for flexible control over the scale of the texture and allows simultaneous matching against multiple levels of an image pyramid created from the texture sample. We use graph cuts for texture transfer, adapting this scheme to the context of surface synthesis. The resulting surface textures are realistic, tolerant of local mesh detail and are comparable to results produced by texture neighbourhood sampling approaches.

Reliable graph discovery

A critical question in data mining is that can we always trust what discovered by a data mining system unconditionally? The answer is obviously not. If not, when can we trust the discovery then? What are the factors that affect the reliability of the discovery? How do they affect the reliability of the discovery? These are some interesting questions to be investigated. In this chapter we will firstly provide a definition and the measurements of reliability, and analyse the factors that affect the reliability. We then examine the impact of model complexity, weak links, varying sample sizes and the ability of different learners to the reliability of graphical model discovery. The experimental results reveal that (1) the larger sample size for the discovery, the higher reliability we will get; (2) the stronger a graph link is, the easier the discovery will be and thus the higher the reliability it can achieve; (3) the complexity of a graph also plays an important role in the discovery. The higher the complexity of a graph is, the more difficult to induce the graph and the lower reliability it would be. We also examined the performance difference of different discovery algorithms. This reveals the impact of discovery process. The experimental results show the superior reliability and robustness of MML method to standard significance tests in the recovery of graph links with small samples and weak links.

Discovering semantics from visualizations of film takes

In this paper, we study the application of a scene structure visualizing technique called Double-Ring Take-Transition-Diagram (DR-TTD). This technique presents takes and their transitions during a film scene via nodes and edges of a 'graph' consisting of two rings as its backbone. We describe how certain filmic elements such as montage, centre/cutaway, dialogue, temporal flow, zone change, dramatic progression, shot association, scene introduction, scene resolution, master shot and editing orchestration can be identified from a scene through the signature arrangements of nodes and edges in the DR-TTD.

Isomery of SU3 states in the strictly restricted dynamics model

Employing the general principles of classification of SU3 states, we have found 285 quantum number isomers (QNI), i.e. nuclei for which there are two possible SU3 quantum number sets, characterized by the maximal eigenvalue of the SU3 group Casimir operator, at the minimal value N-0(min) for the quantum number N-0 of the group U3(A-1) symmetric representation, allowed by the Pauli principle. 41 of these QNI can be attributed to the nun-excited, ground SU3 configurations of realistic nuclei. Two examples of QNI: Si-28 and Zn-60, have been studied in detail in the framework of the strictly restricted dynamics model (SRDM).