Log in

Relevant bibliographies by topics / Random weighted graphs / Journal articles

To see the other types of publications on this topic, follow the link: Random weighted graphs.

Journal articles on the topic 'Random weighted graphs'

Author: Grafiati

Published: 14 December 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Random weighted graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Komjáthy, Júlia, and Bas Lodewijks. "Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs." Stochastic Processes and their Applications 130, no. 3 (March 2020): 1309–67. http://dx.doi.org/10.1016/j.spa.2019.04.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Vengerovsky, V. "Eigenvalue Distribution of Bipartite Large Weighted Random Graphs. Resolvent Approach." Zurnal matematiceskoj fiziki, analiza, geometrii 12, no. 1 (March 25, 2016): 78–93. http://dx.doi.org/10.15407/mag12.01.078.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Davis, Michael, Zhanyu Ma, Weiru Liu, Paul Miller, Ruth Hunter, and Frank Kee. "Generating Realistic Labelled, Weighted Random Graphs." Algorithms 8, no. 4 (December 8, 2015): 1143–74. http://dx.doi.org/10.3390/a8041143.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Amini, Hamed, Moez Draief, and Marc Lelarge. "Flooding in Weighted Sparse Random Graphs." SIAM Journal on Discrete Mathematics 27, no. 1 (January 2013): 1–26. http://dx.doi.org/10.1137/120865021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Amini, Hamed, and Marc Lelarge. "The diameter of weighted random graphs." Annals of Applied Probability 25, no. 3 (June 2015): 1686–727. http://dx.doi.org/10.1214/14-aap1034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ganesan, Ghurumuruhan. "Weighted Eulerian extensions of random graphs." Gulf Journal of Mathematics 16, no. 2 (April 12, 2024): 1–11. http://dx.doi.org/10.56947/gjom.v16i2.1866.

Full text

Abstract:

The Eulerian extension number of any graph H (i.e. the minimum number of edges needed to be added to make H Eulerian) is at least t(H), half the number of odd degree vertices of H. In this paper we consider weighted Eulerian extensions of a random graph G where we add edges of bounded weights and use an iterative probabilistic method to obtain sufficient conditions for the weighted Eulerian extension number of G to grow linearly with t(G). We derive our conditions in terms of the average edge probabilities and edge density and also show that bounded extensions are rare by estimating the skewness of a fixed weighted extension. Finally, we briefly describe a decomposition involving Eulerian extensions of G to convert a large dataset into small dissimilar batches.

APA, Harvard, Vancouver, ISO, and other styles

7

Porfiri, Maurizio, and Daniel J. Stilwell. "Consensus Seeking Over Random Weighted Directed Graphs." IEEE Transactions on Automatic Control 52, no. 9 (September 2007): 1767–73. http://dx.doi.org/10.1109/tac.2007.904603.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Khorunzhy, O., M. Shcherbina, and V. Vengerovsky. "Eigenvalue distribution of large weighted random graphs." Journal of Mathematical Physics 45, no. 4 (April 2004): 1648–72. http://dx.doi.org/10.1063/1.1667610.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Mountford, Thomas, and Jacques Saliba. "Flooding and diameter in general weighted random graphs." Journal of Applied Probability 57, no. 3 (September 2020): 956–80. http://dx.doi.org/10.1017/jpr.2020.45.

Full text

Abstract:

AbstractIn this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of vertices n tends to infinity, in the case where the weight distribution G has an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds.

APA, Harvard, Vancouver, ISO, and other styles

10

Mosbah, M., and N. Saheb. "Non-uniform random spanning trees on weighted graphs." Theoretical Computer Science 218, no. 2 (May 1999): 263–71. http://dx.doi.org/10.1016/s0304-3975(98)00325-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

DeMuse, Ryan, and Mei Yin. "Dimension reduction in vertex-weighted exponential random graphs." Physica A: Statistical Mechanics and its Applications 561 (January 2021): 125289. http://dx.doi.org/10.1016/j.physa.2020.125289.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Chang, Xiao, Hao Xu, and Shing-Tung Yau. "Spanning trees and random walks on weighted graphs." Pacific Journal of Mathematics 273, no. 1 (January 1, 2015): 241–55. http://dx.doi.org/10.2140/pjm.2015.273.241.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

DeMuse, Ryan, Terry Easlick, and Mei Yin. "Mixing time of vertex-weighted exponential random graphs." Journal of Computational and Applied Mathematics 362 (December 2019): 443–59. http://dx.doi.org/10.1016/j.cam.2018.07.038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Stephan, Ludovic, and Laurent Massoulié. "Non-backtracking spectra of weighted inhomogeneous random graphs." Mathematical Statistics and Learning 5, no. 3 (December 21, 2022): 201–71. http://dx.doi.org/10.4171/msl/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Csaba, Béla, and András Pluhár. "A Weighted Regularity Lemma with Applications." International Journal of Combinatorics 2014 (June 19, 2014): 1–9. http://dx.doi.org/10.1155/2014/602657.

Full text

Abstract:

We prove an extension of the regularity lemma with vertex and edge weights which in principle can be applied for arbitrary graphs. The applications involve random graphs and a weighted version of the Erdős-Stone theorem. We also provide means to handle the otherwise uncontrolled exceptional set.

APA, Harvard, Vancouver, ISO, and other styles

16

Bobrowski, Omer, and Primoz Skraba. "Cluster Persistence for Weighted Graphs." Entropy 25, no. 12 (November 26, 2023): 1587. http://dx.doi.org/10.3390/e25121587.

Full text

Abstract:

Persistent homology is a natural tool for probing the topological characteristics of weighted graphs, essentially focusing on their 0-dimensional homology. While this area has been thoroughly studied, we present a new approach to constructing a filtration for cluster analysis via persistent homology. The key advantages of the new filtration is that (a) it provides richer signatures for connected components by introducing non-trivial birth times, and (b) it is robust to outliers. The key idea is that nodes are ignored until they belong to sufficiently large clusters. We demonstrate the computational efficiency of our filtration, its practical effectiveness, and explore into its properties when applied to random graphs.

APA, Harvard, Vancouver, ISO, and other styles

17

Baroni, Enrico, Remco van der Hofstad, and Júlia Komjáthy. "Nonuniversality of weighted random graphs with infinite variance degree." Journal of Applied Probability 54, no. 1 (March 2017): 146–64. http://dx.doi.org/10.1017/jpr.2016.92.

Full text

Abstract:

AbstractWe prove nonuniversality results for first-passage percolation on the configuration model with independent and identically distributed (i.i.d.) degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviours are possible. When the weights are almost surely larger than a constant, the weight and number of edges in the graph grow proportionally to log log n, as for the graph distances. On the other hand, when the continuous-time branching process describing the first-passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the continuous-time processes started from the two sources. This nonuniversality is in sharp contrast to the setting where the degree sequence has a finite variance, Bhamidi et al. (2012).

APA, Harvard, Vancouver, ISO, and other styles

18

Gabrysch, Katja. "Convergence of directed random graphs to the Poisson-weighted infinite tree." Journal of Applied Probability 53, no. 2 (June 2016): 463–74. http://dx.doi.org/10.1017/jpr.2016.13.

Full text

Abstract:

Abstract We consider a directed graph on the integers with a directed edge from vertex i to j present with probability n-1, whenever i < j, independently of all other edges. Moreover, to each edge (i, j) we assign weight n-1(j - i). We show that the closure of vertex 0 in such a weighted random graph converges in distribution to the Poisson-weighted infinite tree as n → ∞. In addition, we derive limit theorems for the length of the longest path in the subgraph of the Poisson-weighted infinite tree which has all vertices at weighted distance of at most ρ from the root.

APA, Harvard, Vancouver, ISO, and other styles

19

Nadutkina, A. V., A. N. Tikhomirov, and D. A. Timushev. "Marchenko–Pastur Law for Spectra of Random Weighted Bipartite Graphs." Siberian Advances in Mathematics 34, no. 2 (May 31, 2024): 146–53. http://dx.doi.org/10.1134/s1055134424020056.

Full text

Abstract:

Abstract We study the spectra of random weighted bipartite graphs. We establish that, under specific assumptions on the edge probabilities, the symmetrized empirical spectral distribution function of the graph’s adjacency matrix converges to the symmetrized Marchenko-Pastur distribution function.

APA, Harvard, Vancouver, ISO, and other styles

20

Goldmakher, Leo, Cap Khoury, Steven J. Miller, and Kesinee Ninsuwan. "On the spectral distribution of large weighted random regular graphs." Random Matrices: Theory and Applications 03, no. 04 (October 2014): 1450015. http://dx.doi.org/10.1142/s2010326314500154.

Full text

Abstract:

McKay proved the limiting spectral measures of the ensembles of d-regular graphs with N vertices converge to Kesten's measure as N → ∞. Given a large d-regular graph we assign random weights, drawn from some distribution [Formula: see text], to its edges. We study the relationship between [Formula: see text] and the associated limiting spectral distribution obtained by averaging over the weighted graphs. We establish the existence of a unique "eigendistribution" (a weight distribution [Formula: see text] such that the associated limiting spectral distribution is a rescaling of [Formula: see text]). Initial investigations suggested that the eigendistribution was the semi-circle distribution, which by Wigner's Law is the limiting spectral measure for real symmetric matrices. We prove this is not the case, though the deviation between the eigendistribution and the semi-circular density is small (the first seven moments agree, and the difference in each higher moment is O(1/d2)). Our analysis uses combinatorial results about closed acyclic walks in large trees, which may be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

21

Huillet, Thierry. "Random walks pertaining to a class of deterministic weighted graphs." Journal of Physics A: Mathematical and Theoretical 42, no. 27 (June 11, 2009): 275001. http://dx.doi.org/10.1088/1751-8113/42/27/275001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Yong, Zhang, Siyu Chen, Hong Qin, and Ting Yan. "Directed weighted random graphs with an increasing bi-degree sequence." Statistics & Probability Letters 119 (December 2016): 235–40. http://dx.doi.org/10.1016/j.spl.2016.08.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Coppersmith, Don, Peter Doyle, Prabhakar Raghavan, and Marc Snir. "Random walks on weighted graphs and applications to on-line algorithms." Journal of the ACM 40, no. 3 (July 1993): 421–53. http://dx.doi.org/10.1145/174130.174131.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Dieker, A. B. "Interlacings for Random Walks on Weighted Graphs and the Interchange Process." SIAM Journal on Discrete Mathematics 24, no. 1 (January 2010): 191–206. http://dx.doi.org/10.1137/090775361.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Hu, Ganglin, and Jun Pang. "Relation-Aware Weighted Embedding for Heterogeneous Graphs." Information Technology and Control 52, no. 1 (March 28, 2023): 199–214. http://dx.doi.org/10.5755/j01.itc.52.1.32390.

Full text

Abstract:

Heterogeneous graph embedding, aiming to learn the low-dimensional representations of nodes, is effective in many tasks, such as link prediction, node classification, and community detection. Most existing graph embedding methods conducted on heterogeneous graphs treat the heterogeneous neighbours equally. Although it is possible to get node weights through attention mechanisms mainly developed using expensive recursive message-passing, they are difficult to deal with large-scale networks. In this paper, we propose R-WHGE, a relation-aware weighted embedding model for heterogeneous graphs, to resolve this issue. R-WHGE comprehensively considers structural information, semantic information, meta-paths of nodes and meta-path-based node weights to learn effective node embeddings. More specifically, we first extract the feature importance of each node and then take the nodes’ importance as node weights. A weighted random walks-based embedding learning model is proposed to generate the initial weighted node embeddings according to each meta-path. Finally, we feed these embeddings to a relation-aware heterogeneous graph neural network to generate compact embeddings of nodes, which captures relation-aware characteristics. Extensive experiments on real-world datasets demonstrate that our model is competitive against various state-of-the-art methods.

APA, Harvard, Vancouver, ISO, and other styles

26

Alonso, L., J. A. Méndez-Bermúdez, A. González-Meléndrez, and Yamir Moreno. "Weighted random-geometric and random-rectangular graphs: spectral and eigenfunction properties of the adjacency matrix." Journal of Complex Networks 6, no. 5 (October 30, 2017): 753–66. http://dx.doi.org/10.1093/comnet/cnx053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Cushing, David, Supanat Kamtue, Shiping Liu, Florentin Münch, Norbert Peyerimhoff, and Ben Snodgrass. "Bakry–Émery Curvature Sharpness and Curvature Flow in Finite Weighted Graphs. Implementation." Axioms 12, no. 6 (June 11, 2023): 577. http://dx.doi.org/10.3390/axioms12060577.

Full text

Abstract:

In this paper, we discuss the implementation of a curvature flow on weighted graphs based on the Bakry–Émery calculus. This flow can be adapted to preserve the Markovian property and its limits as time goes to infinity turn out to be curvature sharp weighted graphs. After reviewing some of the main results of the corresponding paper concerned with the theoretical aspects, we present various examples (random graphs, paths, cycles, complete graphs, wedge sums and Cartesian products of complete graphs, and hypercubes) and exhibit various properties of this flow. One particular aspect of our investigations is asymptotic stability and instability of curvature flow equilibria. The paper ends with a description of the Python functions and routines freely available in an ancillary file on arXiv or via github. We hope that the explanations of the Python implementation via examples will help users to carry out their own curvature flow experiments.

APA, Harvard, Vancouver, ISO, and other styles

28

Wade, Andrew R. "Explicit laws of large numbers for random nearest-neighbour-type graphs." Advances in Applied Probability 39, no. 2 (June 2007): 326–42. http://dx.doi.org/10.1239/aap/1183667613.

Full text

Abstract:

Under the unifying umbrella of a general result of Penrose and Yukich (Annals of Applied Probability13 (2003), 277-303) we give laws of large numbers (in the Lp sense) for the total power-weighted length of several nearest-neighbour-type graphs on random point sets in ℝd, d ∈ ℕ. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest-neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

APA, Harvard, Vancouver, ISO, and other styles

29

Marenco, Bernardo, Paola Bermolen, Marcelo Fiori, Federico Larroca, and Gonzalo Mateos. "Online Change Point Detection for Weighted and Directed Random Dot Product Graphs." IEEE Transactions on Signal and Information Processing over Networks 8 (2022): 144–59. http://dx.doi.org/10.1109/tsipn.2022.3149098.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

DeMuse, Ryan, Danielle Larcomb, and Mei Yin. "Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality." Journal of Statistical Physics 171, no. 1 (February 28, 2018): 127–44. http://dx.doi.org/10.1007/s10955-018-1991-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Bertacchi, Daniela, and Fabio Zucca. "Critical Behaviors and Critical Values of Branching Random Walks on Multigraphs." Journal of Applied Probability 45, no. 2 (June 2008): 481–97. http://dx.doi.org/10.1239/jap/1214950362.

Full text

Abstract:

We consider weak and strong survival for branching random walks on multigraphs with bounded degree. We prove that, at the strong critical value, the process dies out locally almost surely. We relate the weak critical value to a geometric parameter of the multigraph. For a large class of multigraphs (which enlarges the class of quasi-transitive or regular graphs), we prove that, at the weak critical value, the process dies out globally almost surely. Moreover, for the same class, we prove that the existence of a pure weak phase is equivalent to nonamenability. The results are extended to branching random walks on weighted graphs.

APA, Harvard, Vancouver, ISO, and other styles

32

Wade, Andrew R. "Explicit laws of large numbers for random nearest-neighbour-type graphs." Advances in Applied Probability 39, no. 02 (June 2007): 326–42. http://dx.doi.org/10.1017/s0001867800001786.

Full text

Abstract:

Under the unifying umbrella of a general result of Penrose and Yukich (Annals of Applied Probability 13 (2003), 277-303) we give laws of large numbers (in the L p sense) for the total power-weighted length of several nearest-neighbour-type graphs on random point sets in ℝ d , d ∈ ℕ. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest-neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

APA, Harvard, Vancouver, ISO, and other styles

33

Bertacchi, Daniela, and Fabio Zucca. "Critical Behaviors and Critical Values of Branching Random Walks on Multigraphs." Journal of Applied Probability 45, no. 02 (June 2008): 481–97. http://dx.doi.org/10.1017/s002190020000437x.

Full text

Abstract:

We consider weak and strong survival for branching random walks on multigraphs with bounded degree. We prove that, at the strong critical value, the process dies out locally almost surely. We relate the weak critical value to a geometric parameter of the multigraph. For a large class of multigraphs (which enlarges the class of quasi-transitive or regular graphs), we prove that, at the weak critical value, the process dies out globally almost surely. Moreover, for the same class, we prove that the existence of a pure weak phase is equivalent to nonamenability. The results are extended to branching random walks on weighted graphs.

APA, Harvard, Vancouver, ISO, and other styles

34

Chen, Ningyuan, and Mariana Olvera-Cravioto. "Coupling on weighted branching trees." Advances in Applied Probability 48, no. 2 (June 2016): 499–524. http://dx.doi.org/10.1017/apr.2016.12.

Full text

Abstract:

Abstract In this paper we consider linear functions constructed on two different weighted branching processes and provide explicit bounds for their Kantorovich–Rubinstein distance in terms of couplings of their corresponding generic branching vectors. Motivated by applications to the analysis of random graphs, we also consider a variation of the weighted branching process where the generic branching vector has a different dependence structure from the usual one. By applying the bounds to sequences of weighted branching processes, we derive sufficient conditions for the convergence in the Kantorovich–Rubinstein distance of linear functions. We focus on the case where the limits are endogenous fixed points of suitable smoothing transformations.

APA, Harvard, Vancouver, ISO, and other styles

35

Khosoussi, Kasra, Matthew Giamou, Gaurav S. Sukhatme, Shoudong Huang, Gamini Dissanayake, and Jonathan P. How. "Reliable Graphs for SLAM." International Journal of Robotics Research 38, no. 2-3 (January 22, 2019): 260–98. http://dx.doi.org/10.1177/0278364918823086.

Full text

Abstract:

Estimation-over-graphs (EoG) is a class of estimation problems that admit a natural graphical representation. Several key problems in robotics and sensor networks, including sensor network localization, synchronization over a group, and simultaneous localization and mapping (SLAM) fall into this category. We pursue two main goals in this work. First, we aim to characterize the impact of the graphical structure of SLAM and related problems on estimation reliability. We draw connections between several notions of graph connectivity and various properties of the underlying estimation problem. In particular, we establish results on the impact of the weighted number of spanning trees on the D-optimality criterion in 2D SLAM. These results enable agents to evaluate estimation reliability based only on the graphical representation of the EoG problem. We then use our findings and study the problem of designing sparse SLAM problems that lead to reliable maximum likelihood estimates through the synthesis of sparse graphs with the maximum weighted tree connectivity. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, we establish several new theoretical results, including the monotone log-submodularity of the weighted number of spanning trees. We exploit these structures and design a complementary greedy–convex pair of efficient approximation algorithms with provable guarantees. The proposed synthesis framework is applied to various forms of the measurement selection problem in resource-constrained SLAM. Our algorithms and theoretical findings are validated using random graphs, existing and new synthetic SLAM benchmarks, and publicly available real pose-graph SLAM datasets.

APA, Harvard, Vancouver, ISO, and other styles

36

Liitiäinen, Elia, Amaury Lendasse, and Francesco Corona. "Bounds on the mean power-weighted nearest neighbour distance." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 464, no. 2097 (April 15, 2008): 2293–301. http://dx.doi.org/10.1098/rspa.2007.0234.

Full text

Abstract:

In this paper, bounds on the mean power-weighted nearest neighbour distance are derived. Previous work concentrates mainly on the infinite sample limit, whereas our bounds hold for any sample size. The results are expected to be of importance, for example in statistical physics, non-parametric statistics and computational geometry, where they are related to the structure of matter as well as properties of statistical estimators and random graphs.

APA, Harvard, Vancouver, ISO, and other styles

37

Andres, Sebastian, Jean-Dominique Deuschel, and Martin Slowik. "Harnack inequalities on weighted graphs and some applications to the random conductance model." Probability Theory and Related Fields 164, no. 3-4 (March 25, 2015): 931–77. http://dx.doi.org/10.1007/s00440-015-0623-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Bramburger, Jason J. "Stability of infinite systems of coupled oscillators via random walks on weighted graphs." Transactions of the American Mathematical Society 372, no. 2 (March 20, 2019): 1159–92. http://dx.doi.org/10.1090/tran/7609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

SIENKIEWICZ, JULIAN, and JANUSZ A. HOŁYST. "SCALING OF INTERNODE DISTANCES IN WEIGHTED COMPLEX NETWORKS." International Journal of Modern Physics C 21, no. 06 (June 2010): 731–39. http://dx.doi.org/10.1142/s0129183110015439.

Full text

Abstract:

We extend the previously observed scaling equation connecting the internode distances and nodes' degrees onto the case of weighted networks. We show that the scaling takes a similar form in the empirical data obtained from networks characterized by different relations between node's strength and its degree. In the case of explicit equation for s (k) (e.g. linear or scale-free), the new coefficients of scaling equation can be easily obtained. We support our analysis with numerical simulations for Erdös–Rényi random graphs with different weight distributions.

APA, Harvard, Vancouver, ISO, and other styles

40

GAMARNIK, DAVID, and DAVID A. GOLDBERG. "Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections." Combinatorics, Probability and Computing 19, no. 1 (June 22, 2009): 61–85. http://dx.doi.org/10.1017/s0963548309990186.

Full text

Abstract:

We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant-degree regular graphs. We show that forr-regular graphs withnnodes and girth at leastg, the algorithm finds an independent set of expected cardinalitywheref(r) is a function which we explicitly compute. A similar result is established for matchings. Our results imply improved bounds for the size of the largest independent set in these graphs, and provide the first results of this type for matchings. As an implication we show that the greedy algorithm returns a nearly perfect matching when both the degreerand girthgare large. Furthermore, we show that the cardinality of independent sets and matchings produced by the greedy algorithm inarbitrarybounded-degree graphs is concentrated around the mean. Finally, we analyse the performance of the greedy algorithm for the case of random i.i.d. weighted independent sets and matchings, and obtain a remarkably simple expression for the limiting expected values produced by the algorithm. In fact, all the other results are obtained as straightforward corollaries from the results for the weighted case.

APA, Harvard, Vancouver, ISO, and other styles

41

Cuadra, Lucas, and José Carlos Nieto-Borge. "Modeling Quantum Dot Systems as Random Geometric Graphs with Probability Amplitude-Based Weighted Links." Nanomaterials 11, no. 2 (February 2, 2021): 375. http://dx.doi.org/10.3390/nano11020375.

Full text

Abstract:

This paper focuses on modeling a disorder ensemble of quantum dots (QDs) as a special kind of Random Geometric Graphs (RGG) with weighted links. We compute any link weight as the overlap integral (or electron probability amplitude) between the QDs (=nodes) involved. This naturally leads to a weighted adjacency matrix, a Laplacian matrix, and a time evolution operator that have meaning in Quantum Mechanics. The model prohibits the existence of long-range links (shortcuts) between distant nodes because the electron cannot tunnel between two QDs that are too far away in the array. The spatial network generated by the proposed model captures inner properties of the QD system, which cannot be deduced from the simple interactions of their isolated components. It predicts the system quantum state, its time evolution, and the emergence of quantum transport when the network becomes connected.

APA, Harvard, Vancouver, ISO, and other styles

42

XING, CHANGMING, and LIN YANG. "RANDOM WALKS IN HETEROGENEOUS WEIGHTED PSEUDO-FRACTAL WEBS WITH THE SAME WEIGHT SEQUENCE." Fractals 27, no. 06 (September 2019): 1950089. http://dx.doi.org/10.1142/s0218348x19500890.

Full text

Abstract:

Intuitively, link weight could affect the dynamics of the network. However, the theoretical research on the effects of link weight on network dynamics is still rare. In this paper, we present two heterogeneous weighted pseudo-fractal webs controlled by two weight parameters [Formula: see text] and [Formula: see text] ([Formula: see text]). Both graph models are scale-free deterministic graphs, and they have the same weight sequence when [Formula: see text] and [Formula: see text] are fixed. Based on their self-similar graph structure, we study the effect of heterogeneous weight on the random walks in graph with scale-free characteristics. We obtain analytically the average trapping time (ATT) for biased random walks in graphs with a trap located at a fixed node. Analyzing and comparing the obtained solutions, we find that in the large graph limit, the ATT for both graph models all grow as a power function of the graph size (number of nodes) with the exponent [Formula: see text] dependents on the ratio of parameters [Formula: see text] and [Formula: see text], but their exponents [Formula: see text] are not the same, one gets the minimum when [Formula: see text], while the other gets the maximum. Furthermore, the average weighted shortest path length (AWSPL) to the trap is calculated for both graph models, respectively. We show that when the graph size tends to infinity, their AWSPL grows unbounded with the graph size for most parameters. We hope that these results could help people understand the impact of heterogeneous weight on network dynamics.

APA, Harvard, Vancouver, ISO, and other styles

43

Luo, Jing, Hong Qin, and Zhenghong Wang. "Asymptotic Distribution in Directed Finite Weighted Random Graphs with an Increasing Bi-Degree Sequence." Acta Mathematica Scientia 40, no. 2 (March 2020): 355–68. http://dx.doi.org/10.1007/s10473-020-0204-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Fernandez, Carlos, Ioannis Vourkas, and Antonio Rubio. "Shortest Path Computing in Directed Graphs with Weighted Edges Mapped on Random Networks of Memristors." Parallel Processing Letters 30, no. 01 (March 2020): 2050002. http://dx.doi.org/10.1142/s0129626420500024.

Full text

Abstract:

To accelerate the execution of advanced computing tasks, in-memory computing with resistive memory provides a promising solution. In this context, networks of memristors could be used as parallel computing medium for the solution of complex optimization problems. Lately, the solution of the shortest-path problem (SPP) in a two-dimensional memristive grid has been given wide consideration. Some still open problems in such computing approach concern the time required for the grid to reach to a steady state, and the time required to read the result, stored in the state of a subset of memristors that represent the solution. This paper presents a circuit simulation-based performance assessment of memristor networks as SPP solvers. A previous methodology was extended to support weighted directed graphs. We tried memristor device models with fundamentally different switching behavior to check their suitability for such applications and the impact on the timely detection of the solution. Furthermore, the requirement of binary vs. analog operation of memristors was evaluated. Finally, the memristor network-based computing approach was compared to known algorithmic solutions to the SPP over a large set of random graphs of different sizes and topologies. Our results contribute to the proper development of bio-inspired memristor network-based SPP solvers.

APA, Harvard, Vancouver, ISO, and other styles

45

Parodi, Pietro, and Peter Watson. "PROPERTY GRAPHS – A STATISTICAL MODEL FOR FIRE AND EXPLOSION LOSSES BASED ON GRAPH THEORY." ASTIN Bulletin 49, no. 2 (March 27, 2019): 263–97. http://dx.doi.org/10.1017/asb.2019.4.

Full text

Abstract:

AbstractIt is rare that the severity loss distribution for a specific line of business can be derived from first principles. One such example is the use of generalised Pareto distribution for losses above a large threshold (or more accurately: asymptotically), which is dictated by extreme value theory. Most popular distributions, such as the lognormal distribution or the Maxwell-Boltzmann-Bose-Einstein-Fermi-Dirac (MBBEFD), are convenient heuristics with no underlying theory to back them. This paper presents a way to derive a severity distribution for property losses based on modelling a property as a weighted graph, that is, a collection of nodes and weighted arcs connecting these nodes. Each node v (to which a value can also be assigned) corresponds to a room or a unit of the property where a fire can occur, while an arc (v, v′; p) between vertices v and v′ signals that the probability of the fire propagating from v to v′ is p. The paper presents two simple models for fire propagation (the random graph approach and the random time approach) and a model for explosion risk that allow one to calculate the loss distribution for a given property from first principles. The MBBEFD model is shown to be a good approximation for the simulated distribution of losses based on property graphs for both the random graph and the random time approach.

APA, Harvard, Vancouver, ISO, and other styles

46

FROESE, RICHARD, DAVID HASLER, and WOLFGANG SPITZER. "ABSOLUTELY CONTINUOUS SPECTRUM FOR A RANDOM POTENTIAL ON A TREE WITH STRONG TRANSVERSE CORRELATIONS AND LARGE WEIGHTED LOOPS." Reviews in Mathematical Physics 21, no. 06 (July 2009): 709–33. http://dx.doi.org/10.1142/s0129055x09003724.

Full text

Abstract:

We consider random Schrödinger operators on tree graphs and prove absolutely continuous spectrum at small disorder for two models. The first model is the usual binary tree with certain strongly correlated random potentials. These potentials are of interest since for complete correlation they exhibit localization at all disorders. In the second model, we change the tree graph by adding all possible edges to the graph inside each sphere, with weights proportional to the number of points in the sphere.

APA, Harvard, Vancouver, ISO, and other styles

47

DAUDERT, BRITTA, and MICHEL L. LAPIDUS. "LOCALIZATION ON SNOWFLAKE DOMAINS." Fractals 15, no. 03 (September 2007): 255–72. http://dx.doi.org/10.1142/s0218348x0700354x.

Full text

Abstract:

The geometric features of the square and triadic Koch snowflake drums are compared using a position entropy defined on the grid points of the discretizations (prefractals) of the two domains. Weighted graphs using the geometric quantities are created and random walks on the two prefractals are performed. The aim is to understand if the existence of narrow channels in the domain may cause the "localization" of eigenfunctions.

APA, Harvard, Vancouver, ISO, and other styles

48

Srinivasan, Sriram, Behrouz Babaki, Golnoosh Farnadi, and Lise Getoor. "Lifted Hinge-Loss Markov Random Fields." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7975–83. http://dx.doi.org/10.1609/aaai.v33i01.33017975.

Full text

Abstract:

Statistical relational learning models are powerful tools that combine ideas from first-order logic with probabilistic graphical models to represent complex dependencies. Despite their success in encoding large problems with a compact set of weighted rules, performing inference over these models is often challenging. In this paper, we show how to effectively combine two powerful ideas for scaling inference for large graphical models. The first idea, lifted inference, is a wellstudied approach to speeding up inference in graphical models by exploiting symmetries in the underlying problem. The second idea is to frame Maximum a posteriori (MAP) inference as a convex optimization problem and use alternating direction method of multipliers (ADMM) to solve the problem in parallel. A well-studied relaxation to the combinatorial optimization problem defined for logical Markov random fields gives rise to a hinge-loss Markov random field (HLMRF) for which MAP inference is a convex optimization problem. We show how the formalism introduced for coloring weighted bipartite graphs using a color refinement algorithm can be integrated with the ADMM optimization technique to take advantage of the sparse dependency structures of HLMRFs. Our proposed approach, lifted hinge-loss Markov random fields (LHL-MRFs), preserves the structure of the original problem after lifting and solves lifted inference as distributed convex optimization with ADMM. In our empirical evaluation on real-world problems, we observe up to a three times speed up in inference over HL-MRFs.

APA, Harvard, Vancouver, ISO, and other styles

49

Bouamama, Salim, Christian Blum, and Pedro Pinacho-Davidson . "A Population-Based Iterated Greedy Algorithm for Maximizing Sensor Network Lifetime." Sensors 22, no. 5 (February 24, 2022): 1804. http://dx.doi.org/10.3390/s22051804.

Full text

Abstract:

Finding dominating sets in graphs is very important in the context of numerous real-world applications, especially in the area of wireless sensor networks. This is because network lifetime in wireless sensor networks can be prolonged by assigning sensors to disjoint dominating node sets. The nodes of these sets are then used by a sleep–wake cycling mechanism in a sequential way; that is, at any moment in time, only the nodes from exactly one of these sets are switched on while the others are switched off. This paper presents a population-based iterated greedy algorithm for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Our approach is compared to the ILP solver, CPLEX, which is an existing local search technique, and to our earlier greedy algorithm. This is performed through its application to 640 random graphs from the literature and to 300 newly generated random geometric graphs. The results show that our algorithm significantly outperforms the competitors.

APA, Harvard, Vancouver, ISO, and other styles

50

Mattie, Heather, and Jukka-Pekka Onnela. "Edge overlap in weighted and directed social networks." Network Science 9, no. 2 (February 16, 2021): 179–93. http://dx.doi.org/10.1017/nws.2020.49.

Full text

Abstract:

AbstractWith the increasing availability of behavioral data from diverse digital sources, such as social media sites and cell phones, it is now possible to obtain detailed information about the structure, strength, and directionality of social interactions in varied settings. While most metrics of network structure have traditionally been defined for unweighted and undirected networks only, the richness of current network data calls for extending these metrics to weighted and directed networks. One fundamental metric in social networks is edge overlap, the proportion of friends shared by two connected individuals. Here, we extend definitions of edge overlap to weighted and directed networks and present closed-form expressions for the mean and variance of each version for the Erdős–Rényi random graph and its weighted and directed counterparts. We apply these results to social network data collected in rural villages in southern Karnataka, India. We use our analytical results to quantify the extent to which the average overlap of the empirical social network deviates from that of corresponding random graphs and compare the values of overlap across networks. Our novel definitions allow the calculation of edge overlap for more complex networks, and our derivations provide a statistically rigorous way for comparing edge overlap across networks.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!