| Large-scale complex networks have been the objects of study for the past two decades, and two problems have been the main focus: constructing or designing realistic models for large-scale networks and making statistical inferences in such networks. These problems appear in a variety of research areas including coding theory, combinatorial optimization, and biological systems. This thesis explains the use of the techniques Sequential Importance Sampling (SIS) and Belief Propagation (BP) for designing and making inferences in large-scale networks.; This manuscript starts with an algorithm for designing random graphs that is an important tool in simulating protocols on Internet topology and detecting motifs in genetic networks. Unfortunately, the existing algorithms for this problem have large running times, making them impractical to use for networks with thousands of vertices. Our approach is based on SIS that has been recently introduced as a successful heuristic for counting graphs. We analyze validity of SIS and obtain the fastest algorithm for generating random graphs with given degree sequences.; The second portion of this thesis will be about a mysterious message-passing algorithm called Belief Propagation (BP). Despite spectacular success of the BP in inference on large-scale networks, theoretical results concerning the correctness and convergence of the method are known only in few cases. We will prove correctness and convergence of the BP for finding maximum weight matching in bipartite graphs. This also yields a simple and distributed algorithm and offers the possibility of implementation in hardware for scheduling in high speed routers. |
