Kenth Engø-Monsen

Abstract: We study the properties of the principal eigenvector for the adjacency matrix (and related matrices) for a general directed graph. In particular�motivated by the use of the eigenvector for estimating the �importance� of the nodes in the graph�we focus on the distribution of positive weight in this eigenvector, and give a coherent picture which builds upon and unites earlier results. We also propose a simple method��T-Rank��for generating importance scores. T-Rank generates authority scores via a one-level, non-normalized matrix, and is thus distinct from known methods such as PageRank (normalized), HITS (two-level), and SALSA (two-level and normalized). We show, using our understanding of the principal eigenvector, that T-Rank has a much less severe �sink problem� than does PageRank. Also, we offer numerical results which quantify the �tightly-knit community� or TKC effect. We find that T-Rank has a stronger TKC effect than PageRank, and we offer a novel interpolation method which allows for continuous tuning of the strength of this TKC effect. Finally, we propose two new �sink remedies�, i.e., methods for ensuring that the principal eigenvector is positive everywhere. One of our sink remedies (source pumping) is unique among sink remedies, in that it gives a positive eigenvector without rendering the graph strongly connected. We offer a preliminary evaluation of the effects and possible applications of these new sink remedies.

Abstract: In this paper we offer a topology-driven ([`]natural') definition of subclusters of an undirected graph or network. In addition we find rules for assigning unique roles (from a small set of possible roles) to each node in the network. Our approach is based on the use of a [`]smooth' index for well-connectedness (eigenvector centrality) which is computed for each node. This index, viewed as a height function, then guides the decomposition of the graph into regions (associated with local peaks of the index), and borders (valleys) between regions. We propose and compare two rules for assigning nodes to regions. We illustrate our approach with simple test graphs, and also by applying it to snapshots of the Gnutella peer-to-peer network from late 2001. This latter analysis suggests that our method implies novel ways of interpreting the notion of well-connectedness for a graph, as these snapshots represent very well connected networks. We argue that our approach is well suited for analyzing computer networks, towards the goal of enhancing their security.

Abstract: We describe a model of computer security that applies results from the statistical properties of graphs to human-computer systems. The model attempts to determine a safe threshold of interconnectivity in a human-computer system by ad hoc network analyses. The results can be applied to physical networks, social networks and networks of clues in a forensic analysis. Access control, intrusions and social engineering can also be discussed as graph- and information-theoretical relationships. Groups of users and shared objects, such as files or conversations, provide communication channels for the spread of both authorized and unauthorized information. We present numerical criteria for measuring the security of such systems and algorithms for finding the vulnerable points.

Abstract: We introduce partitioned Runge�Kutta (PRK) methods as geometric integrators in the Runge�Kutta�Munthe-Kaas (RKMK) method hierarchy. This is done by first noticing that tangent and cotangent bundles are the natural domains for the differential equations to be solved. Next, we equip the (co)tangent bundle of a Lie group with a group structure and treat it as a Lie group. The structure of the differential equations on the (co)tangent-bundle Lie group is such that partitioned versions of the RKMK methods are naturally introduced. Numerical examples are included to illustrate the new methods.

Abstract: We find local closed-form expression for the Baker�Campbell�Hausdorff formula in the Lie algebra so(3), and interpret the formula geometrically in terms of rotation vectors in �3.

Abstract: In the past few years, a number of Lie-group methods based on Runge�Kutta schemes have been proposed. One might extrapolate that using a selfadjoint Runge�Kutta scheme yields a Lie-group selfadjoint scheme, but this is generally not the case: Lie-group methods depend on the choice of a coordinate chart which might fail to comply to selfadjointness.

Abstract: We describe an object-oriented MATLAB toolbox for solving differential equations on manifolds. The software reflects recent development within the area of geometric integration. Through the use of elements from differential geometry, in particular Lie groups and homogeneous spaces, coordinate free formulations of numerical integrators are developed. The strict mathematical definitions and results are well suited for implementation in an object-oriented language, and, due to its simplicity, the authors have chosen MATLAB as the working environment. The basic ideas of DiffMan are presented, along with particular examples that illustrate the working of and the theory behind the software package.

Abstract: In Multibody System Dynamics2, 71�88, wedescribed the Munthe-Kaas and Crouch�Grossman methods for integratingordinary differential equations numerically on Lie groups. We used theheavy top as a special test problem, and showed that the numericalsolution respects the configuration space TSO(3). We were, however, notable to generate numerical solutions that preserved the first integralsof the top. In this paper, we formulate the heavy top equations on amore natural configuration space, and show that both the Munthe-Kaas andthe Crouch�Grossman methods with suitable coefficient sets can generatenumerical solutions that render first integrals to machine accuracy. Asa partial answer to the comment in �Concluding Remarks� inMultibody System Dynamics2, 71�88, we also argue that forHamiltonian systems on the dual space of a Lie algebra, theinfinitesimal generator map describing the differential equation for thecoadjoint action is the functional derivative of the Hamiltonian.

Abstract: We consider the construction of geometric integrators in the class of RKMK methods. Any differential equation in the form of an infinitesimal generator on a homogeneous space is shown to be locally equivalent to a differential equation on the Lie algebra corresponding to the Lie group acting on the homogeneous space. This way we obtain a distinction between the coordinate-free phrasing of the differential equation and the local coordinates used. In this paper we study methods based on arbitrary local coordinates on the Lie group manifold. By choosing the coordinates to be canonical coordinates of the first kind we obtain the original method of Munthe-Kaas [16]. Methods similar to the RKMK method are developed based on the different coordinatizations of the Lie group manifold, given by the Cayley transform, diagonal Padé approximants of the exponential map, canonical coordinates of the second kind, etc. Some numerical experiments are also given.

Abstract: We apply Munthe-Kaas and Crouch�Grossman methods in the solution of some mechanical problems. These methods are quite new, and they exploit intrinsic properties of the manifolds defined by the mechanical problems, thus ensuring that the numerical solution obey underlying constraints. A brief introduction to the methods is presented, and numerical simulations show some of the properties they possess. We also discuss error estimation and stepsize selection for some of these methods.

Abstract: The World Wide Web consists of a vast amount of information in the form of web-pages. Almost all subjects are covered somewhere in the billions of pages reachable from your computer. To access this enormous library from our computers is a wonderful thing � but the tremendous size of the web is also a problem. With an ever-growing number of pages covering all sorts of subjects, it becomes very hard to �nd the one, relevant piece of information you need. Web link analysis is a tool which assists us with this task. It helps us to rank web documents, and so to �nd the most important documents among the huge amount of irrelevant information available online. The input to the web link analysis is a network of hyperlinked documents, where the nodes are documents, and the directed edges are hyperlinks from one page to another. The output is a vector containing a numerical score which represents the importance of each page in the Web graph. A typical use of this score is to assist ranking of a search engine query result. The most well-known example is the search engine Google, which uses a web-link analysis algorithm developed by Brin and Page [68]. In this article we will present an overview of the principal existing methods used to calculate importance scores for Web pages, using the Web graph as input. We will discuss the theory behind the different approaches, compare them to each other, and discuss some selected practical and technical problems with Web link analysis.

Abstract: The problem of epidemic spreading over networks has received considerable attention in recent years, due both to its intrinsic intellectual challenge and to its practical importance. A good recent summary of such work may be found in Newman (8), while (9) gives an outstanding example of a non-trivial prediction which is obtained from explicitly modeling the network in the epidemic spreading. In the language of mathematicians and computer scientists, a network of nodes connected by edges is called a graph. Most work on epidemic spreading over networks focuses on whole-graph properties, such as the percentage of infected nodes at long time. Two of us have, in contrast, focused on understanding the spread of an infection over time and space (the network) (61; 63; 62). This work involves decomposing any given network into subgraphs called regions (61). Regions are precisely defined as disjoint subgraphs which may be viewed as coarse-grained units of infection�in that, once one node in a region is infected, the progress of the infection over the remainder of the region is relatively fast and predictable (63). We note that this approach is based on the �Susceptible-Infected� (SI) model of infection, in which nodes, once infected, are never cured. This model is reasonable for some infections, such as HIV�which is one of the diseases studied here. We also study gonorrhea and chlamydia, for which a more appropriate model is Susceptible-Infected-Susceptible (SIS) (67) (since nodes can be cured); we discuss the limitations of our approach for these cases below.

Abstract:

Abstract: The dominant eigenvector of matrices defined by weighted links in overlay networks plays an important role in many peer-to-peer applications. Examples include trust management, importance ranking to support search, and virtual coordinate systems to facilitate managing network proximity. Robust and efficient asynchronous distributed algorithms are known only for the case when the dominant eigenvalue is exactly one. We present a fully distributed algorithm for a more general case: non-negative square matrices that have an arbitrary dominant eigenvalue. The basic idea is that we apply a gossip-based aggregation protocol coupled with an asynchronous iteration algorithm, where the gossip component controls the iteration component. The norm of the resulting vector is an unknown finite constant by default; however, it can optionally be set to any desired constant using a third gossip control component. Through extensive simulation results on artificially generated overlay networks and real web traces we demonstrate the correctness, the performance and the fault tolerance of the protocol.

Abstract: We present qualitative arguments concerning the probable infection pattern in a directed graph under the (weak or strong) influence of the outside world. This question is relevant for real computer viruses, which spread by following the (logical) directed links formed by address lists. Our arguments build on previous work in two (seemingly unrelated) areas: epidemic spreading on undirected graphs, and eigenvectors of directed graphs as applied to Web page ranking. More specifically, we borrow a recently proven result (used to design a �sink remedy� for Web link analysis) and use it to argue for a threshold effect: that the effects of the outside world will not appear in the pattern of infection until the strength of the influence of the outside world exceeds a finite threshold value. We briefly discuss possible tests of this prediction, and its implications.

Abstract: In this chapter we introduce a model for analyzing the spread of epidemics in a disconnected mobile network. The work is based on an extension, to a dynamic setting, of the eigenvector centrality principle introduced by two of the authors for the case of static networks. The extension builds on a new definition of connectivity matrix for a highly partitioned mobile system, where the connectivity between a pair of nodes is defined as the number of contacts taking place over a finite time window. The connectivity matrix is then used to evaluate the eigenvector centrality of the various nodes. Numerical results from real-world traces are presented and discussed. The applicability of the proposed approach to select on-line message forwarders is also addressed

Abstract: To understand the diffusive spreading of a product in a telecom network, whether the product is a service, handset, or subscription, it can be very useful to study the structure of the underlying social network. By combining mobile traffic data and product adoption history from one of Telenor's markets, we can define and measure an adoption network-roughly, the social network of adopters. By studying the time evolution of adoption networks, we can observe how different products diffuses through the network, and measure potential social influence. This paper presents an empirical and comparative study of three adoption networks evolving over time in a large telecom network. We believe that the strongest spreading of adoption takes place in the dense core of the underlying network, and gives rise to a dominant largest connected component (LCC) in the adoption network, which we call �the social network monster�. We believe that the size of the monster is a good indicator for whether or not a product is taking off. We show that the evolution of the LCC, and the size distribution of the other components, vary strongly with different products. The products studied in this article illustrate three distinct cases: that the social network monsters can grow or break down over time, or fail to occur at all. Some of the reasons a product takes off are intrinsic to the product; there are also aspects of the broader social context that can play in. Tentative explanations are offered for these phenomena. Also, we present two statistical tests which give an indication of the strength of the spreading over the social network. We find evidence that the spreading is dependent on the underlying social network, in particular for the early adopters.

Abstract:

Abstract: