_We introduce a new graph parameter called the burning number, inspired by contact processes on graphs such as bootstrap percolation, and searching paradigms Firefighter. The number measures speed of spread contagion in graph; lower faster spreads. We provide properties including characterizations bounds. is computed for several classes, derived generated Iterated Local Transitivity model social networks_.

We present a new stochastic model for complex networks, based on spatial embedding of the nodes, called _spatial preferred attachment_ (SPA) model. In SPA model, nodes have influence regions varying size, and may link to node only if they fall within its region. The models background knowledge or identity node, which will environment. our can determine their environment local network. prove that gives power-law in-degree distribution, with exponent in [2,∞) depending parameters,...

In this paper we show that the list chromatic index of complete graph K n is at most . This proves list-chromatic conjecture for graphs odd order. We also prove asymptotic result a simple with maximum degree d exceeds by [Oscr ]( 2/3 √log ).

Several network models have been proposed to explain the link structure observed in online social networks. This paper addresses problem of choosing model that best fits a given real-world network. We implement model-selection method based on unsupervised learning. An alternating decision tree is trained using synthetic graphs generated according each under consideration. use broad array features, with aim representing different structural aspects Features include frequency counts small...

We study the link structure of online social networks (OSNs) and introduce a new model for such that may help in inferring their hidden underlying reality. In geo-protean (GEO-P) OSNs, nodes are identified with points Euclidean space, edges stochastically generated by mixture relative distance ranking function. With high probability, GEO-P generates graphs satisfying many observed properties as power-law degree distributions, small-world property, densification power law, bad spectral...

We study the link structure of on-line social networks (OSNs), and introduce a new model for such which may help infer their hidden underlying reality. In geo-protean (GEO-P) OSNs nodes are identified with points in Euclidean space, edges stochastically generated by mixture relative distance ranking function. With high probability, GEO-P generates graphs satisfying many observed properties OSNs, as power law degree distributions, small world property, densification law, bad spectral...

A Focused crawler must use information gleaned from previously crawled page sequences to estimate the relevance of a newly seen URL. Therefore, good performance depends on powerful modelling context as well current observations. Probabilistic models, such Hidden Markov Models(HMMs) and Conditional Random Fields(CRFs), can potentially capture both formatting context. In this paper, we present HMM for focused web crawling, compare it with Best-First strategy. Furthermore, discuss concept using...

The Dinitz conjecture states that, for each <italic>n</italic> and every collection of <italic>n</italic>-element sets <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript i j"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>i</mml:mi> <mml:mi>j</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">{S_{ij}}</mml:annotation> </mml:semantics> </mml:math>...

Abstract We derive attainable upper bounds on the algebraic connectivity (spectral gap) of a regular graph in terms its diameter and girth. This bound agrees with well‐known Alon–Boppana–Friedman for graphs even diameter, but is an improvement odd diameter. For girth bound, we show that only Moore can attain it, these exist special cases. use combination stochastic algorithms exhaustive search to find which it. 3‐regular graphs, all diameters up including (the case open). These are extremely...

For a number of binary cyclic codes with e>e/sub BCH/, algebraic algorithms are given to find the error locator polynomial. Thus, for these more errors can be corrected algebraically than by Berlekamp-Massey algorithm. In some cases, all patterns weight up e decoded; in other only e' e/sub BCH/<e'<or=e decoded. The correctness three is (partly) based on an exhaustive computer search; proof detail. It seems likely that many decoded methods.<<ETX>>

Several stochastic models were proposed recently to model the dynamic evolution of web graph. We study infinite limits processes graph when time goes infinity. prove that deterministic variations so-called copying can lead several nonisomorphic limits. Some converge random _R_, while convergence other is sensitive initial conditions or minor changes in rules model. explain how share properties with _R_ seem reflect known