728
Analyzing and modelling the AS-level Internet topology
Recently we introduced the rich-club phenomenon as a quantitative metric to characterize the tier structure of the Autonomous Systems level Internet topology (AS graph) and we proposed the Interactive Growth (IG) model, which closely matches the degree distribution and hierarchical structure of the AS graph and compares favourble with other available Internet power-law topology generators. Our research was based on the widely used BGP AS graph obtained from the Oregon BGP routing tables. Researchers argue that Traceroute AS graph, extracted from the traceroute data collected by the CAIDA's active probing tool, Skitter, is more complete and reliable. To be prudent, in this paper we analyze and compare topological structures of Traceroute AS graph and BGP AS graph. Also we compare with two synthetic Internet topologies generated by the IG model and the well-known Barabasi-Albert (BA) model. Result shows that both AS graphs show the rich-club phenomenon and have similar tier structures, which are closely matched by the IG model, however the BA model does not show the rich-club phenomenon at all.
10758103
Accurately modeling the Internet topology
Based on measurements of the internet topology data, we found that there are two mechanisms which are necessary for the correct modeling of the internet topology at the autonomous systems (AS) level: the interactive growth of new nodes and new internal links, and a nonlinear preferential attachment, where the preference probability is described by a positive-feedback mechanism. Based on the above mechanisms, we introduce the positive-feedback preference (PFP) model which accurately reproduces many topological properties of the AS-level internet, including degree distribution, rich-club connectivity, the maximum degree, shortest path length, short cycles, disassortative mixing, and betweenness centrality. The PFP model is a phenomenological model which provides an insight into the evolutionary dynamics of real complex networks.
3804246
The missing links in the BGP-based AS connectivity maps
PAM2003 - The Passive and Active Measurement Workshop(http://www.pam2003.org), San Diego, USA, April 2003
1466117
Redundancy and Robustness of the AS-level Internet topology and its models
A comparison between the topological properties of the measured Internet topology, at the autonomous system level (AS graph), and the equivalent graphs generated by two different power law topology generators are presented. Only one of the synthetic generators reproduces the tier connectivity of the AS graph.
25346055
Almost Covers Of 2-Arc Transitive Graphs
Let Γ be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition ℬ with block size v. Let Γℬ be the quotient graph of Γ relative to ℬ and Γ[B,C] the bipartite subgraph of Γ induced by adjacent blocks B,C of ℬ. In this paper we study such graphs for which Γℬ is connected, (G, 2)-arc transitive and is almost covered by Γ in the sense that Γ[B,C] is a matching of v-1 ≥ 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case Γℬ ≅Kv+1 is covered by results of Gardiner and Praeger. We consider here the general case where Γℬ ≇Kv+1, and prove that, for some even integer n ≥ 4, Γℬ is a near n-gonal graph with respect to a certain G-orbit on n-cycles of Γℬ. Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient Γℬ of a graph with these properties. (A near n-gonal graph is a connected graph Σ of girth at least 4 together with a set ℰ of n-cycles of Σ such that each 2-arc of Σ is contained in a unique member of ℰ.)
29793155
Finite symmetric graphs with two-arc transitive quotients
This paper forms part of a study of 2-arc transitivity for finite imprimitive symmetric graphs, namely for graphs Γ admitting an automorphism group G that is transitive on ordered pairs of adjacent vertices, and leaves invariant a nontrivial vertex partition B. Such a group G is also transitive on the ordered pairs of adjacent vertices of the quotient graph ΓB corresponding to B. If in addition G is transitive on the 2-arcs of Γ (that is, on vertex triples (α, β γ) such that α, β and β, γ are adjacent and α ≠ γ), then G is not in general transitive on the 2-arcs of ΓB, although it does have this property in the special case where B is the orbit set of a vertex-intransitive normal subgroup of G. On the other hand, G is sometimes transitive on the 2-arcs of ΓB even if it is not transitive on the 2-arcs of Γ. We study conditions under which G is transitive on the 2-arcs of ΓB. Our conditions relate to the structure of the bipartite graph induced on B ∪ C for adjacent blocks B, C of B and a graph structure induced on B. We obtain necessary and sufficient conditions for G to be transitive on the 2-arcs of one or both of Γ, ΓB, for certain families of imprimitive symmetric graphs.
1717304
Shape Regression Machine
We present a machine learning approach called shape regression machine (SRM) to segmenting in real time an anatomic structure that manifests a deformable shape in a medical image. Traditional shape segmentation methods rely on various assumptions. For instance, the deformable model assumes that edge defines the shape; the Mumford-Shah variational method assumes that the regions inside/outside the (closed) contour are homogenous in intensity; and the active appearance model assumes that shape/appearance variations are linear. In addition, they all need a good initialization. In contrast, SRM poses no such restrictions. It is a two-stage approach that leverages (a) the underlying medical context that defines the anatomic structure and (b) an annotated database that exemplifies the shape and appearance variations of the anatomy. In the first stage, it solves the initialization problem as object detection and derives a regression solution that needs just one scan in principle. In the second stage, it learns a nonlinear regressor that predicts the nonrigid shape from image appearance. We also propose a boosting regression approach that supports real time segmentation. We demonstrate the effectiveness of SRM using experiments on segmenting the left ventricle endocardium from an echocardiogram of an apical four chamber view.
61202442
Probabilistic identity characterization for face recognition
We present a general framework for characterizing the object identity in a single image or a group of images with each image containing a transformed version of the object, with applications to face recognition. In terms of the transformation, the group is made of either many still images or frames of a video sequence. The object identity is either discrete- or continuous-valued. This probabilistic framework integrates all the evidence of the set and handles the localization problem, illumination and pose variations through subspace identity encoding. Issues and challenges arising in this framework are addressed and efficient computational schemes are presented. Good face recognition results using the PIE database are reported.
9649594
Probabilistic Human Recognition from Video
This paper presents a method for incorporating temporal information in a video sequence for the task of human recognition. A time series state space model, parameterized by a tracking state vector and a recognizing identity variable, is proposed to simultaneously characterize the kinematics and identity. Two sequential importance sampling (SIS) methods, a brute-force version and an efficient version, are developed to provide numerical solutions to the model. The joint distribution of both state vector and identity variable is estimated at each time instant and then propagated to the next time instant. Marginalization over the state vector yields a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and kinematics, a degeneracy in posterior probability of the identity variable is achieved to give improved recognition. This evolving behavior is characterized using changes in entropy. The effectiveness of this approach is illustrated using experimental results on low resolution face data and upper body data.