Mostrando recursos 1 - 20 de 156

  1. Approximations of the Generalized Inverse of the Graph Laplacian Matrix

    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...

  2. Strategic Coloring of a Graph

    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...

  3. Bistability through Triadic Closure

    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...

  4. Digraph Laplacian and the Degree of Asymmetry

    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,...

  5. Balance in Random Signed Graphs

    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...

  6. Model Selection for Social Networks Using Graphlets

    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...

  7. Mean Commute Time for Random Walks on Hierarchical Scale-Free Networks

    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...

  8. An Extended Stochastic Model for Quantitative Security Analysis of Networked Systems

    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...

  9. Degree Distribution and Number of Edges between Nodes of Given Degrees in the Buckley–Osthus Model of a Random Web Graph

    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...

  10. Moment-Based Estimation of Stochastic Kronecker Graph Parameters

    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.

  11. Monotone Graph Limits and Quasimonotone Graphs

    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...

  12. Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

    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...

  13. Multiplicative Attribute Graph Model of Real-World Networks

    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...

  14. Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz Scores

    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...

  15. Finding and Visualizing Graph Clusters Using PageRank Optimization

    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.

  16. Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising

    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...

  17. Geometric Protean Graphs

    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...

  18. Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

    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...

  19. Multiplicative Attribute Graph Model of Real-World Networks

    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...

  20. Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz Scores

    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...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.