Recursos de colección
Project Euclid (Hosted at Cornell University Library) (192.320 recursos)
Internet Mathematics
Internet Mathematics
Bozzo, Enrico; Franceschet, Massimo
We devise methods for finding approximations of the generalized inverse of
the graph Laplacian matrix, which arises in many graph-theoretic applications. Finding
this matrix in its entirety involves solving a matrix inversion problem, which is resourcedemanding
in terms of consumed time and memory and hence impractical whenever the
graph is relatively large. Our approximations use only a few eigenpairs of the Laplacian
matrix and are parametric with respect to this number, so that the user can compromise
between effectiveness and efficiency of the approximate solution. We apply the devised
approximations to the problem of computing current-flow betweenness centrality on a
graph. However, given the generality of the Laplacian...
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme
We study a strategic game in which every node of a graph is owned by a
player who has to choose a color. A player’s payoff is 0 if at least one neighbor selected
the same color; otherwise, it is the number of players who selected the same color. The
social cost of a state is defined as the number of distinct colors that the players use. It
is ideally equal to the chromatic number of the graph, but it can substantially deviate
because every player cares about his own payoff, however bad the social cost may be.
Following previous work in Panagopoulou and Spirakis, “A...
Grindrod, Peter; Higham, Desmond J.; Parsons, Mark C.
We propose and analyze a class of evolving network models suitable for describing
a dynamic topological structure. Applications include telecommunication, online
social behavior, and information processing in neuroscience. We model the evolving
network as a discrete-time Markov chain and study a very general framework in which
edges conditioned on the current state appear or disappear independently at the next
time step. We show how to exploit symmetries in the microscopic, localized rules in order
to obtain conjugate classes of random graphs that simplify analysis and calibration
of a model. Further, we develop a mean field theory for describing network evolution.
For a simple but realistic scenario incorporating the...
Li, Yanhua; Zhang, Zhi-Li
In this paper we extend and generalize the standard spectral graph theory
(or random-walk theory) on undirected graphs to digraphs. In particular, we introduce
and define a normalized digraph Laplacian (Diplacian for short) $\Gamma$ for digraphs, and
prove that (1) its Moore–Penrose pseudoinverse is the discrete Green’s function of the
Diplacian matrix as an operator on digraphs, and (2) it is the normalized fundamental
matrix of the Markov chain governing random walks on digraphs. Using these results,
we derive a new formula for computing hitting and commute times in terms of the
Moore–Penrose pseudoinverse of the Diplacian, or equivalently, the singular values and
vectors of the Diplacian.
¶ Furthermore,...
El Maftouhi, A.; Manoussakis, Y.; Megalakaki, O.
By extending Heider's and Cartwright–Harary's theory of balance in deterministic
social structures, we study the problem of balance in social structures in which
relations among individuals are random. An appropriate model for representing such
structures is that of random signed graphs $G_{n,p,q}$, defined as follows. Given a set of $n$
vertices and fixed numbers $p$ and $q$, $0 \lt p + q \lt 1$, then between each pair of vertices,
there exists a positive edge, a negative edge, or no edge with respective probabilities $p,
q, 1 − p − q$.
¶ We first show that almost always (i.e., with probability tending to 1 as $n \to...
Janssen, Jeannette; Hurshman, Matt; Kalyaniwalla, Nauzer
Several network models have been proposed to explain the link structure
observed in online social networks. This paper addresses the problem of choosing
the model that best fits a given real-world network. We implement a model-selection
method based on unsupervised learning. An alternating decision tree is trained using
synthetic graphs generated according to each of the models under consideration. We use
a broad array of features, with the aim of representing different structural aspects of the
network. Features include the frequency counts of small subgraphs (graphlets) as well
as features capturing the degree distribution and small-world property. Our method
correctly classifies synthetic graphs, and is robust under perturbations...
Shang, Yilun
In recent years, there has been a surge of research interest in networks with
scale-free topologies, partly due to the fact that they are prevalent in scientific research
and real-life applications. In this paper, we study random-walk issues on a family
of two-parameter scale-free networks, called $(x, y)$-flowers. These networks, which are
constructed in a deterministic recursive fashion, display rich behaviors such as the
small-world phenomenon and pseudofractal properties. We derive analytically the mean
commute times for random walks on $(x, y)$-flowers and show that the mean commute
times scale with the network size as a power-law function with exponent governed
by both parameters $x$ and $y$. We...
Xu, Maochao; Xu, Shouhuai
Quantitative security analysis of networked computer systems has been an
open problem in computer security for decades. Recently, a promising approach was
proposed in Li et al., which, however, made some strong assumptions including
the exponential distribution of, and the independence among, the relevant random
variables. In this paper, we substantially weaken these assumptions while offering, in
addition to the same types of analytical results as in Li et al., methods for obtaining
the desired security quantities in practice. Moreover, we investigate the problem
from a higher-level abstraction, which also leads to both analytical results and practical
methods for obtaining the desired security quantities. These should represent a
significant...
Grechnikov, Evgeniy A.
In this paper, we study some important statistics of the random graph
$H^{(t)}_{a ,k}$
in the Buckley-Osthus model, where $t$ is the number of nodes, $kt$ is the number of
edges (so that $k \in \mathbb{N}$), and $a \gt 0$ is the so-called initial attractiveness of a node. This
model is a modification of the well-known Bollobás-Riordan model. First, we find a
new asymptotic formula for the expectation of the number $R(d, t)$ of nodes of a given
degree $d$ in a graph in this model. Such a formula is known for $a \in \mathbb{N}$ and $d \le t^{1/100(a+1)}$ .
Both restrictions are unsatisfactory from theoretical and...
Gleich, David F.; Owen, Art B.
Stochastic Kronecker graphs supply a parsimonious model for large sparse
real-world graphs. They can specify the distribution of a large random graph using
only three or four parameters. Those parameters have, however, proved difficult to
choose in specific applications. This article looks at method-of-moments estimators
that are computationally much simpler than maximum likelihood. The estimators are
fast, and in our examples, they typically yield Kronecker parameters with expected
feature counts closer to a given graph than we get from KronFit. The improvement is
especially prominent for the number of triangles in the graph.
Bollobás, Bála; Janson, Svante; Riordan, Oliver
The recent theory of graph limits gives a powerful framework for understanding
the properties of suitable (convergent) sequences $(G_n)$ of graphs in terms of
a limiting object that may be represented by a symmetric function $W$ on $[0, 1]^2$ , i.e., a
kernel or graphon. In this context it is natural to wish to relate specific properties of the
sequence to specific properties of the kernel. Here we show that the kernel is monotone
(i.e., increasing in both variables) if and only if the sequence satisfies a “quasimonotonicity”
property defined by a certain functional tending to zero. As a tool we prove
an inequality relating the cut...
Kolountzakis, Mihail N.; Miller, Gary L.; Peng, Richard; Tsourakakis, Charalampos E.
The number of triangles is a computationally expensive graph statistic frequently
used in complex network analysis (e.g., transitivity ratio), in various random
graph models (e.g., exponential random graph model), and in important real-world
applications such as spam detection, uncovering the hidden thematic structures in
the Web, and link recommendation. Counting triangles in graphs with millions and
billions of edges requires algorithms that run fast, use little space, provide accurate
estimates of the number of triangles, and preferably are parallelizable. In this paper we
present an efficient triangle-counting approximation algorithm that can be adapted to
the semistreaming model. Its key idea is to combine the sampling
algorithm of Tsourakakis, and...
Kim, Myunghwan; Leskovec, Jure
Networks are a powerful way to describe and represent social, technological,
and biological systems, where nodes represent entities (people, web sites, genes)
and edges represent interactions (friendships, communication, regulation). The study
of such networks then seeks to find common structural patterns and explain their emergence
through tractable models of network formation.
¶ In most networks, each node is associated with a rich set of attributes or features. For
example, users in online social networks have profile information, genes have properties
and functions, and web pages contain text. However, most existing network models
focus on modeling the network structure while ignoring the features and properties of
the nodes. Thus, the...
Bonchi, Francesco; Esfandiar, Pooya; Gleich, David F.; Greif, Chen; Lakshmanan, Laks V. S.
We explore methods for approximating the commute time and Katz score
between a pair of nodes. These methods are based on the approach of matrices, moments,
and quadrature developed in the numerical linear algebra community. They
rely on the Lanczos process and provide upper and lower bounds on an estimate of the
pairwise scores. We also explore methods to approximate the commute times and Katz
scores from a node to all other nodes in the graph. Here, our approach for the commute
times is based on a variation of the conjugate gradient algorithm, and it provides an
estimate of all the diagonals of the inverse of a...
Chung, Fan; Tsiatas, Alexander
We give algorithms for finding graph clusters and drawing graphs, highlighting
local community structure within the context of a larger network. For a given graph
G, we use the personalized PageRank vectors to determine a set of clusters, by optimizing
the jumping parameter α subject to several cluster variance measures in order
to capture the graph structure according to PageRank. We then give a graph visualization
algorithm for the clusters using PageRank-based coordinates. Several drawings
of real-world data are given, illustrating the partition and local community structure.
Demaine, Erik D.; Zadimoghaddam, Morteza
Network-creation games have been studied recently in many different settings.
These games are motivated by social networks in which selfish agents want to construct
a connection graph among themselves. Each node wants to minimize its average or
maximum distance to the others, without paying much to construct the network. Many
generalizations have been considered, including nonuniform interests between nodes,
general graphs of allowable edges, and bounded-budget agents. In all of these settings,
there is no known constant bound on the price of anarchy. In fact, in many cases, the
price of anarchy can be very large, namely, a constant power of the number of agents.
This means that...
Bonato, Anthony; Janssen, Jeannette; Prałat, Paweł
We study the link structure of online social networks (OSNs) and introduce
a new model for such networks that may help in inferring their hidden underlying reality.
In the geo-protean (GEO-P) model for OSNs, nodes are identified with points in
Euclidean space, and edges are stochastically generated by a mixture of the relative
distance of nodes and a ranking function. With high probability, the GEO-P model
generates graphs satisfying many observed properties of OSNs, such as power-law degree
distributions, the small-world property, densification power law, and bad spectral
expansion. We introduce the dimension of an OSN based on our model and examine
this new parameter using actual OSN...
Kolountzakis, Mihail N.; Miller, Gary L.; Peng, Richard; Tsourakakis, Charalampos E.
The number of triangles is a computationally expensive graph statistic frequently
used in complex network analysis (e.g., transitivity ratio), in various random
graph models (e.g., exponential random graph model), and in important real-world
applications such as spam detection, uncovering the hidden thematic structures in
the Web, and link recommendation. Counting triangles in graphs with millions and
billions of edges requires algorithms that run fast, use little space, provide accurate
estimates of the number of triangles, and preferably are parallelizable. In this paper we
present an efficient triangle-counting approximation algorithm that can be adapted to
the semistreaming model. Its key idea is to combine the sampling
algorithm of Tsourakakis, and...
Kim, Myunghwan; Leskovec, Jure
Networks are a powerful way to describe and represent social, technological,
and biological systems, where nodes represent entities (people, web sites, genes)
and edges represent interactions (friendships, communication, regulation). The study
of such networks then seeks to find common structural patterns and explain their emergence
through tractable models of network formation.
¶ In most networks, each node is associated with a rich set of attributes or features. For
example, users in online social networks have profile information, genes have properties
and functions, and web pages contain text. However, most existing network models
focus on modeling the network structure while ignoring the features and properties of
the nodes. Thus, the...
Bonchi, Francesco; Esfandiar, Pooya; Gleich, David F.; Greif, Chen; Lakshmanan, Laks V. S.
We explore methods for approximating the commute time and Katz score
between a pair of nodes. These methods are based on the approach of matrices, moments,
and quadrature developed in the numerical linear algebra community. They
rely on the Lanczos process and provide upper and lower bounds on an estimate of the
pairwise scores. We also explore methods to approximate the commute times and Katz
scores from a node to all other nodes in the graph. Here, our approach for the commute
times is based on a variation of the conjugate gradient algorithm, and it provides an
estimate of all the diagonals of the inverse of a...