Figure 1.
The path graph $P_3$ on three nodes
-
Previous Article
Superconvergence of the semi-discrete local discontinuous Galerkin method for nonlinear KdV-type problems
- DCDS-B Home
- This Issue
-
Next Article
Preface
January
2019, 24(1): 1-17.
doi: 10.3934/dcdsb.2018161
Modulus metrics on networks
Department of Mathematics, Kansas State University, Manhattan, KS 66506, USA |
The concept of $p$-modulus gives a way to measure the richness of a family of objects on a graph. In this paper, we investigate the families of connecting walks between two fixed nodes and show how to use $p$-modulus to form a parametrized family of graph metrics that generalize several well-known and widely-used metrics. We also investigate a characteristic of metrics called the "antisnowflaking exponent" and present some numerical findings supporting a conjecture about the new metrics. We end with explicit computations of the new metrics on some selected graphs.
Mathematics Subject Classification:
90C35.
Citation:
Nathan Albin, Nethali Fernando, Pietro Poggi-Corradini. Modulus metrics on networks. Discrete & Continuous Dynamical Systems - B,
2019, 24
(1)
: 1-17.
doi: 10.3934/dcdsb.2018161
![]()
References:
| [1] |
N. Albin, J. Clemens, N. Fernando and P. Poggi-Corradini, Blocking duality for p-modulus on networks and applications, arXiv: 1612.00435. Google Scholar |
| [2] |
N. Albin, M. Brunner, R. Perez, P. Poggi-Corradini and N. Wiens,
Modulus on graphs as a generalization of standard graph theoretic quantities, Conform. Geom. Dyn., 19 (2015), 298-317.
doi: 10.1090/ecgd/287. |
| [3] |
N. Albin and P. Poggi-Corradini,
Minimal subfamilies and the probabilistic interpretation for modulus on graphs, J. Anal., 24 (2016), 183-208.
doi: 10.1007/s41478-016-0002-9. |
| [4] |
N. Albin, F. D. Sahneh, M. Goering and P. Poggi-Corradini, Modulus of families of walks on graphs, in Complex Analysis and Dynamical Systems VII, vol. 699 of Contemp. Math., Amer. Math. Soc., Providence, RI, 2017, 35–55.
doi: 10.1090/conm/699/14080. |
| [5] |
G. Csardi and T. Nepusz, The igraph software package for complex network research, InterJournal, Complex Systems (2006), 1695, URL http://igraph.sf.net. Google Scholar |
| [6] |
S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research, 17 (2016), Paper No. 83, 5 pp. |
| [7] |
J. Ding, J. R. Lee and Y. Peres,
Cover times, blanket times, and majorizing measures, Ann. of Math., 175 (2012), 1409-1471.
doi: 10.4007/annals.2012.175.3.8. |
| [8] |
P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, vol. 22 of Carus Mathematical Monographs, Mathematical Association of America, Washington, DC, 1984. |
| [9] |
M. Goering, N. Albin, F. Sahneh, C. Scoglio and P. Poggi-Corradini, Numerical investigation of metrics for epidemic processes on graphs, in 2015 49th Asilomar Conference on Signals, Systems and Computers, 2015, 1317–1322.
doi: 10.1109/ACSSC.2015.7421356. |
| [10] |
E. Jones, T. Oliphant and P. Peterson et al., SciPy: Open source scientific tools for Python, 2001–, URL http://www.scipy.org/, [Online; accessed 2/28/2018]. Google Scholar |
| [11] |
D. A. Levin, Y. Peres and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, 2009, With a chapter by James G. Propp and David B. Wilson. |
| [12] |
D. A. Spielman,
Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.), 54 (2017), 45-61.
doi: 10.1090/bull/1557. |
show all references
References:
| [1] |
N. Albin, J. Clemens, N. Fernando and P. Poggi-Corradini, Blocking duality for p-modulus on networks and applications, arXiv: 1612.00435. Google Scholar |
| [2] |
N. Albin, M. Brunner, R. Perez, P. Poggi-Corradini and N. Wiens,
Modulus on graphs as a generalization of standard graph theoretic quantities, Conform. Geom. Dyn., 19 (2015), 298-317.
doi: 10.1090/ecgd/287. |
| [3] |
N. Albin and P. Poggi-Corradini,
Minimal subfamilies and the probabilistic interpretation for modulus on graphs, J. Anal., 24 (2016), 183-208.
doi: 10.1007/s41478-016-0002-9. |
| [4] |
N. Albin, F. D. Sahneh, M. Goering and P. Poggi-Corradini, Modulus of families of walks on graphs, in Complex Analysis and Dynamical Systems VII, vol. 699 of Contemp. Math., Amer. Math. Soc., Providence, RI, 2017, 35–55.
doi: 10.1090/conm/699/14080. |
| [5] |
G. Csardi and T. Nepusz, The igraph software package for complex network research, InterJournal, Complex Systems (2006), 1695, URL http://igraph.sf.net. Google Scholar |
| [6] |
S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research, 17 (2016), Paper No. 83, 5 pp. |
| [7] |
J. Ding, J. R. Lee and Y. Peres,
Cover times, blanket times, and majorizing measures, Ann. of Math., 175 (2012), 1409-1471.
doi: 10.4007/annals.2012.175.3.8. |
| [8] |
P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, vol. 22 of Carus Mathematical Monographs, Mathematical Association of America, Washington, DC, 1984. |
| [9] |
M. Goering, N. Albin, F. Sahneh, C. Scoglio and P. Poggi-Corradini, Numerical investigation of metrics for epidemic processes on graphs, in 2015 49th Asilomar Conference on Signals, Systems and Computers, 2015, 1317–1322.
doi: 10.1109/ACSSC.2015.7421356. |
| [10] |
E. Jones, T. Oliphant and P. Peterson et al., SciPy: Open source scientific tools for Python, 2001–, URL http://www.scipy.org/, [Online; accessed 2/28/2018]. Google Scholar |
| [11] |
D. A. Levin, Y. Peres and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, 2009, With a chapter by James G. Propp and David B. Wilson. |
| [12] |
D. A. Spielman,
Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.), 54 (2017), 45-61.
doi: 10.1090/bull/1557. |
Figure 2.
Antisnowflaking exponent for different $p$ values
Figure 3.
The cycle graph $C_N$ and the extremal density $\rho^*$ for $\Gamma(a, c)$ and $\Gamma(a, b)$
Figure 4.
$K_6$ - Complete graph on 6 nodes
Figure 6.
The square graph
Figure 8.
Comparisons of times required to compute $d_p$ distances on several square 2D grids for different values of $p$
| [1] |
Donato Patrizia, Andrey Piatnitski. On the effective interfacial resistance through rough surfaces. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1295-1310. doi: 10.3934/cpaa.2010.9.1295 |
| [2] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
| [3] |
Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014 |
| [4] |
Paolo Maremonti. On the Stokes problem in exterior domains: The maximum modulus theorem. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 2135-2171. doi: 10.3934/dcds.2014.34.2135 |
| [5] |
Olha Ivanyshyn. Shape reconstruction of acoustic obstacles from the modulus of the far field pattern. Inverse Problems & Imaging, 2007, 1 (4) : 609-622. doi: 10.3934/ipi.2007.1.609 |
| [6] |
Gerard Thompson. Invariant metrics on Lie groups. Journal of Geometric Mechanics, 2015, 7 (4) : 517-526. doi: 10.3934/jgm.2015.7.517 |
| [7] |
Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143 |
| [8] |
Timothy C. Reluga, Jan Medlock. Resistance mechanisms matter in SIR models. Mathematical Biosciences & Engineering, 2007, 4 (3) : 553-563. doi: 10.3934/mbe.2007.4.553 |
| [9] |
Carlos A. Berenstein and Alain Yger. Residues and effective Nullstellensatz. Electronic Research Announcements, 1996, 2: 82-91. |
| [10] |
Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. |
| [11] |
Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 |
| [12] |
J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 |
| [13] |
John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. |
| [14] |
Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075 |
| [15] |
Martin Bauer, Philipp Harms, Peter W. Michor. Sobolev metrics on shape space of surfaces. Journal of Geometric Mechanics, 2011, 3 (4) : 389-438. doi: 10.3934/jgm.2011.3.389 |
| [16] |
Martin Bauer, Philipp Harms, Peter W. Michor. Sobolev metrics on shape space, II: Weighted Sobolev metrics and almost local metrics. Journal of Geometric Mechanics, 2012, 4 (4) : 365-383. doi: 10.3934/jgm.2012.4.365 |
| [17] |
Hong-Kun Zhang. Free path of billiards with flat points. Discrete & Continuous Dynamical Systems, 2012, 32 (12) : 4445-4466. doi: 10.3934/dcds.2012.32.4445 |
| [18] |
Matthias Gerdts, René Henrion, Dietmar Hömberg, Chantal Landry. Path planning and collision avoidance for robots. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 437-463. doi: 10.3934/naco.2012.2.437 |
| [19] |
Piotr Bajger, Mariusz Bodzioch, Urszula Foryś. Singularity of controls in a simple model of acquired chemotherapy resistance. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2039-2052. doi: 10.3934/dcdsb.2019083 |
| [20] |
Urszula Ledzewicz, Heinz Schättler. Drug resistance in cancer chemotherapy as an optimal control problem. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 129-150. doi: 10.3934/dcdsb.2006.6.129 |
2020 Impact Factor: 1.327
Tools
Metrics
Other articles
by authors
[Back to Top]