No description available.

This research report is submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in part fulfillment of the requirements for the degree of Master of Science / The title of this research report is a "A Survey of the most recent State of-the-Art Shortest path algorithms" One may ask what is the need and aim of this survey. During the decades of the 1970's and 1980's there has been considerable research and publication in shortest path algorithm. Each new publication is either a new and faster algorithm or survey of recent methods. ( Abbreviation abstract ) / AC2017

This thesis focuses on a new graphon-based approach for fitting models to large networks and establishes a general framework for incorporating nodal attributes to modeling. The scale of network data nowadays, renders classical network modeling and inference inappropriate. Novel modeling strategies are required as well as estimation methods. Depending on whether the model structure is specified a priori or solely determined from data, existing models for networks can be classified as parametric and non-parametric. Compared to the former, a non-parametric model often allows for an easier and more straightforward estimation procedure of the network structure. On the other hand, the connectivities and dynamics of networks fitted by non-parametric models can be quite difficult to interpret, as compared to parametric models. In this thesis, we first propose a computational estimation procedure for a class of parametric models that are among the most widely used models for networks, built upon tools from non-parametric models with practical innovations that make it efficient and capable of scaling to large networks. Extensions of this base method are then considered in two directions. Inspired by a popular network sampling method, we further propose an estimation algorithm using sampled data, in order to circumvent the practical obstacle that the entire network data is hard to obtain and analyze. The base algorithm is also generalized to consider the case of complex network structure where nodal attributes are involved. Two general frameworks of a non-parametric model are proposed in order to incorporate nodal impact, one with a hierarchical structure, and the other employs similarity measures. Several simulation studies are carried out to illustrate the improved performance of our proposed methods over existing algorithms. The proposed methods are also applied to several real data sets, including Slashdot online social networks and in-school friendship networks from the National Longitudinal Study of Adolescent to Adult Health (AddHealth Study). An array of graphical visualizations and quantitative diagnostic tools, which are specifically designed for the evaluation of goodness of fit for network models, are developed and illustrated with these data sets. Some observations of using these tools via our algorithms are also examined and discussed.

No description available.

No description available.

No description available.

iii, 122 leaves : ill., tables ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Applied Mathematics, 1977

69 leaves : tables ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Applied Mathematics, 1979

Thesis (master's)--Dalhousie University (Canada), 2003. / Adviser: Uday Venkatadri. Includes bibliographical references.

The objective of this thesis is to develop and computationally test a new algorithm for the class of network models with generalized upper bound (GUB) side constraints. Various algorithms have been developed to solve the network with arbitrary side constraints problem; however, no algorithm that exploits the special structure of the GUB side constraints previously existed. The proposed algorithm solves the network with GUB side constraints problem using two sequences of problems. One sequence yields a lower bound on the optimal value for the problem by using a Lagrangean relaxation based on relaxing copies of some subset of the original variables. This is achieved by first solving a pure network subproblem and then solving a set of single constraint bounded variable linear programs. Because only the cost coefficients change from one pure network subproblem to another, the optimal solution for one subproblem is at least feasible, if not optimal, for the next pure network subproblem. The second sequence yields an upper bound on the optimal value by using a decomposition of the problem based on changes in the capacity vector. Solving for the decomposed problem corresponds to solving for pure network subproblems that have undergone changes in lower and/or upper bounds. Recently developed reoptimization techniques are incorporated in the algorithm to find an initial (artificial) feasible solution to the pure network subproblem. A program is developed for solving the network with GUB side constraints problem by using the relaxation and decomposition techniques. The algorithm has been tested on problems with up to 200 nodes, 2000 arcs and 100 GUB constraints. Computational experience indicates that the upper bound procedure seems to perform well; however, the lower bound procedure has a fairly slow convergence rate. It also indicates that the lower bound step size, the initial lower bound value, and the lower and upper bound iteration strategies have a significant effect on the convergence rate of the lower bound algorithm. / Graduation date: 1990