1 |
Generation and properties of random graphs and analysis of randomized algorithmsGao, Pu January 2010 (has links)
We study a new method of generating random $d$-regular graphs by
repeatedly applying an operation called pegging. The pegging
algorithm, which applies the pegging operation in each step, is a
method of generating large random regular graphs beginning with
small ones. We prove that the limiting joint distribution of the
numbers of short cycles in the resulting graph is independent
Poisson. We use the coupling method to bound the total variation
distance between the joint distribution of short cycle counts and
its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound
of the $\eps$-mixing time. The coupling involves two different,
though quite similar, Markov chains that are not time-homogeneous.
We also show that the $\epsilon$-mixing time is not
$o(\epsilon^{-1})$. This demonstrates that the upper bound
is essentially tight. We study also the
connectivity of random $d$-regular graphs generated by the pegging
algorithm. We show that these graphs are asymptotically almost
surely $d$-connected for any even constant $d\ge 4$.
The problem of orientation of random hypergraphs is motivated by the
classical load balancing problem. Let $h>w>0$ be two fixed integers.
Let $\orH$ be a hypergraph whose hyperedges are uniformly of size
$h$.
To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its
vertices positive signs with respect to this hyperedge, and the rest
negative. A $(w,k)$-orientation of $\orH$ consists of a
$w$-orientation of all hyperedges of $\orH$, such that each vertex
receives at most $k$ positive signs from its incident hyperedges.
When $k$ is large enough, we determine the threshold of the
existence of a $(w,k)$-orientation of a random hypergraph. The
$(w,k)$-orientation of hypergraphs is strongly related to a general
version of the off-line load balancing problem.
The other topic we discuss is computing the probability of induced
subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph
on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the
probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$
is $H$. The result holds for any $d=o(n^{1/3})$ and is further
extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of
random graphs with given degree sequence $\bf d$. This result
provides a basic tool for studying properties, for instance the
existence or the counts, of certain types of induced subgraphs.
|
2 |
Generation and properties of random graphs and analysis of randomized algorithmsGao, Pu January 2010 (has links)
We study a new method of generating random $d$-regular graphs by
repeatedly applying an operation called pegging. The pegging
algorithm, which applies the pegging operation in each step, is a
method of generating large random regular graphs beginning with
small ones. We prove that the limiting joint distribution of the
numbers of short cycles in the resulting graph is independent
Poisson. We use the coupling method to bound the total variation
distance between the joint distribution of short cycle counts and
its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound
of the $\eps$-mixing time. The coupling involves two different,
though quite similar, Markov chains that are not time-homogeneous.
We also show that the $\epsilon$-mixing time is not
$o(\epsilon^{-1})$. This demonstrates that the upper bound
is essentially tight. We study also the
connectivity of random $d$-regular graphs generated by the pegging
algorithm. We show that these graphs are asymptotically almost
surely $d$-connected for any even constant $d\ge 4$.
The problem of orientation of random hypergraphs is motivated by the
classical load balancing problem. Let $h>w>0$ be two fixed integers.
Let $\orH$ be a hypergraph whose hyperedges are uniformly of size
$h$.
To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its
vertices positive signs with respect to this hyperedge, and the rest
negative. A $(w,k)$-orientation of $\orH$ consists of a
$w$-orientation of all hyperedges of $\orH$, such that each vertex
receives at most $k$ positive signs from its incident hyperedges.
When $k$ is large enough, we determine the threshold of the
existence of a $(w,k)$-orientation of a random hypergraph. The
$(w,k)$-orientation of hypergraphs is strongly related to a general
version of the off-line load balancing problem.
The other topic we discuss is computing the probability of induced
subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph
on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the
probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$
is $H$. The result holds for any $d=o(n^{1/3})$ and is further
extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of
random graphs with given degree sequence $\bf d$. This result
provides a basic tool for studying properties, for instance the
existence or the counts, of certain types of induced subgraphs.
|
3 |
The Ising Model on a Random Graph Applied to Interacting Agents on the Financial MarketKarlson, Ida January 2007 (has links)
<p>In this thesis we present a model of the interacting agents on the financial market. The agents are represented by a non-Euclidean random graph, where each agent communicate with another with probability p, and the interaction according to the Ising Model. We investigate properties of the model by direct calculations for small graph sizes, and by perfect simulation for larger graph sizes. We also present a model for asset price variation by using the magnetization of the Ising model.</p>
|
4 |
A simulation-based approach to assess the goodness of fit of Exponential Random Graph ModelsLi, Yin 11 1900 (has links)
Exponential Random Graph Models (ERGMs) have been developed for fitting social network
data on both static and dynamic levels. However, the lack of large sample asymptotic
properties makes it inadequate in assessing the goodness-of-fit of these ERGMs.
Simulation-based goodness-of-fit plots were proposed by Hunter et al (2006), comparing
the structured statistics of observed network with those of corresponding simulated
networks. In this research, we propose an improved approach to assess the goodness of fit of
ERGMs. Our method is shown to improve the existing graphical techniques. We also propose a simulation based test
statistic with which the model comparison can be easily achieved. / Biostatistics
|
5 |
A simulation-based approach to assess the goodness of fit of Exponential Random Graph ModelsLi, Yin Unknown Date
No description available.
|
6 |
The Ising Model on a Random Graph Applied to Interacting Agents on the Financial MarketKarlson, Ida January 2007 (has links)
In this thesis we present a model of the interacting agents on the financial market. The agents are represented by a non-Euclidean random graph, where each agent communicate with another with probability p, and the interaction according to the Ising Model. We investigate properties of the model by direct calculations for small graph sizes, and by perfect simulation for larger graph sizes. We also present a model for asset price variation by using the magnetization of the Ising model.
|
7 |
Unravel the Geometry and Topology behind Noisy NetworksTian, Minghao January 2020 (has links)
No description available.
|
8 |
Product Dimension of a Random GraphCooper, Jeffrey R. 28 April 2010 (has links)
No description available.
|
9 |
An approach to Graph Isomorphism using Spanning Trees generated by Breadth First SearchIlchenko, Alexey 29 August 2014 (has links)
No description available.
|
10 |
Models for Systemic RiskShao, Quentin H. January 2017 (has links)
Systemic risk is the risk that an economic shock may result in the breakdown of the fundamental functions of the financial system. It can involve multiple vectors of infection such as chains of losses or consecutive failures of financial institutions that may ultimately cause the failure of the financial system to provide liquidity, stable prices, and to perform economic activities. This thesis develops methods to quantify systemic risk, its effect on the financial system and perhaps more importantly, to determine its cause.
In the first chapter, we provide an overview and a literature review of the topics covered in this thesis. First, we present a literature review on network-based models of systemic risk. Finally we end the first chapter with a review on market impact models.
In the second chapter, we consider one unregulated financial institution with constant absolute risk aversion investment risk preferences that optimizes its strategies in a multi asset market impact model with temporary and permanent impact. We prove the existence and derive explicitly the optimal trading strategies. Furthermore, we conduct numerical exploration on the sensitivity of the optimal trading curve. This chapter sets the foundation for further research into multi-agent models and systemic risk models with optimal behaviours.
In the third chapter, we extend the market impact models to the multi-agent setting. The agents follow a game theoretic strategy that is constrained by the regulations imposed. Furthermore, the agents must liquidate themselves if they become insolvent or unable to meet the regulations imposed on them. This paper provides a bridge between market impact models and network models of systemic risk.
In chapter four, we introduce a financial network model that combines the default and liquidity stress mechanisms into a ``double cascade mapping''. Unlike simpler models, this model can quantify how illiquidity or default of one bank influences the overall level of liquidity stress and default in the system. We derive large-network asymptotic cascade mapping formulas that can be used for efficient network computations of the double cascade. Finally we use systemic risk measures to compare the results of including with and without an asset firesale mechanism. / Thesis / Doctor of Philosophy (PhD)
|
Page generated in 0.0529 seconds