13207643
Towards Modelling The Internet Topology - The Interactive Growth Model
The Internet topology at the Autonomous Systems level (AS graph) has a power-law degree distribution and a tier structure. In this paper, we introduce the Interactive Growth (IG) model based on the joint growth of new nodes and new links. This simple and dynamic model compares favorable with other Internet power-law topology generators because it not only closely resembles the degree distribution of the AS graph, but also accurately matches the hierarchical structure, which is measured by the recently reported rich-club phenomenon.
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.
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.
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.
15470334
Probabilistic recognition of human faces from video
Recognition of human faces using a gallery of still or video images and a probe set of videos is systematically investigated using a probabilistic framework. In still-to-video recognition, where the gallery consists of still images, a time series state space model is proposed to fuse temporal information in a probe video, which simultaneously characterizes the kinematics and identity using a motion vector and an identity variable, respectively. The joint posterior distribution of the motion vector and the identity variable is estimated at each time instant and then propagated to the next time instant, Marginalization over the motion vector yields a robust estimate of the posterior distribution of the identity variable. A computationally efficient sequential importance sampling (SIS) algorithm is developed to estimate the posterior distribution. Empirical results demonstrate that, due to the propagation of the identity variable over time, a degeneracy in posterior probability of the identity variable is achieved to give improved recognition. The gallery is generalized to videos in order to realize video-to-video recognition. An exemplar-based learning strategy is adopted to automatically select video representatives from the gallery, serving as mixture centers in an updated likelihood measure. The SIS algorithm is applied to approximate the posterior distribution of the motion vector, the identity variable, and the exemplar index, whose marginal distribution of the identity variable produces the recognition result. The model formulation is very general and it allows a variety of image representations and transformations. Experimental results using images/videos collected at UMD, NIST/USF, and CMU with pose/illumination variations illustrate the effectiveness of this approach for both still-to-video and video-to-video scenarios with appropriate model choices.
14780024
Fuzzy causal networks: general model, inference, and convergence
In this paper, we first propose a general framework for fuzzy causal networks (FCNs). Then, we study the dynamics and convergence of such general FCNs. We prove that any general FCN with constant weight matrix converges to a limit cycle or a static state, or the trajectory of the FCN is not repetitive. We also prove that under certain conditions a discrete state general FCN converges to its limit cycle or static state in O(n) steps, where n is the number of vertices of the FCN. This is in striking contrast with the exponential running time 2/sup n/, which is accepted widely for classic FCNs.
8505547
Face recognition from video: a CONDENSATION approach
The aim of this work is to investigate how to exploit the temporal information in a video sequence for the task of face recognition. Following the approach in (Li and Chellappa, 2000), we propose a probabilistic model parameterized by a tracking state vector and a recognizing identity variable, simultaneously characterizing the kinematics and identity of humans. We then invoke a CONDENSATION (Isard and Blake, 1996) approach to provide a numerical solution to the model. Once the joint posterior distribution of the state vector and the identity variable is estimated, we marginalize it over the state vector to yield a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and dynamics, a degeneracy in the posterior distribution 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 video data.
18154847
Dynamic domination in fuzzy causal networks
This paper presents a dynamic domination theory for fuzzy causal networks (FCN). There are three major contributions. First, we propose a new inference procedure based on dominating sets. Second, we introduce the concepts of dynamic and minimal dynamic dominating sets (DDS and MDDS) in an FCN. To reflect changes of dominance with time, we also introduce the concept of a dynamic dominating process (DDP) that has significant implications in many real-world problems. We pay a special attention to the minimal dynamic dominating process (MDDP) and develop rules for generating DDP and MDDP. Third, we investigate dynamic dominating sets with extended feedback, which we call effective dynamic dominating sets (EDDS), and related effective dynamic dominating process (EDDP). This study unveils a very important phenomenon in FCN: At any time t, either an EDDS exists or there is a dramatic change of the states of vertices. In the latter case we also identify the special structure of the sub-FCN induced by active vertices.
2387693
Labelling Cayley Graphs on Abelian Groups
For given integers $j \ge k \ge 1$, an $L(j,k)$-labelling of a graph $\Ga$ is an assignment of labels---nonnegative integers---to the vertices of $\Ga$ such that adjacent vertices receive labels that differ by at least $j$, and vertices distance two apart receive labels that differ by at least $k$. The span of such a labelling is the difference between the largest and the smallest labels used, and the minimum span over all $L(j,k)$-labellings of $\Ga$ is denoted by $\l_{j,k}(\Ga)$. The minimum number of labels needed in an $L(j,k)$-labelling of $\Ga$ is independent of $j$ and $k$, and is denoted by $\mu(\Ga)$. In this paper we introduce a general approach to $L(j,k)$-labelling Cayley graphs $\Ga$ over Abelian groups and deriving upper bounds for $\l_{j,k}(\Ga)$ and $\mu(\Ga)$. Using this approach we obtain upper bounds on $\l_{j,k}(\Ga)$ and $\mu(\Ga)$ for graphs $\Ga$ admitting a vertex-transitive Abelian group of automorphisms. Hypercubes $Q_d$ are examples of such graphs, and as consequences we obtain upper bounds for $\l_{j,k}(Q_d)$ and $\mu(Q_d)$. We also obtain the exact values of $\l_{j,k}(\Ga)$ ($2k \ge j \ge k$) and $\mu(\Ga)$ for some Hamming graphs $\Ga$. The result shows that, under certain arithmetic conditions, these two invariants rely only on $k$ and the orders of the two largest complete graph factors of the Hamming graph.