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] |
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 |
| [3] |
Paolo Maremonti. On the Stokes problem in exterior domains: The maximum modulus theorem. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 2135-2171. doi: 10.3934/dcds.2014.34.2135 |
| [4] |
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 |
| [5] |
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 |
| [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] |
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 |
| [8] |
Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. |
| [9] |
Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 |
| [10] |
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 |
| [11] |
John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. |
| [12] |
Carlos A. Berenstein and Alain Yger. Residues and effective Nullstellensatz. Electronic Research Announcements, 1996, 2: 82-91. |
| [13] |
Hong-Kun Zhang. Free path of billiards with flat points. Discrete & Continuous Dynamical Systems - A, 2012, 32 (12) : 4445-4466. doi: 10.3934/dcds.2012.32.4445 |
| [14] |
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 |
| [15] |
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 |
| [16] |
Sebastian Bonhoeffer, Pia Abel zur Wiesch, Roger D. Kouyos. Rotating antibiotics does not minimize selection for resistance. Mathematical Biosciences & Engineering, 2010, 7 (4) : 919-922. doi: 10.3934/mbe.2010.7.919 |
| [17] |
Cristian Tomasetti, Doron Levy. An elementary approach to modeling drug resistance in cancer. Mathematical Biosciences & Engineering, 2010, 7 (4) : 905-918. doi: 10.3934/mbe.2010.7.905 |
| [18] |
Avner Friedman, Najat Ziyadi, Khalid Boushaba. A model of drug resistance with infection by health care workers. Mathematical Biosciences & Engineering, 2010, 7 (4) : 779-792. doi: 10.3934/mbe.2010.7.779 |
| [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] |
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 |
2018 Impact Factor: 1.008
Tools
Metrics
Other articles
by authors
[Back to Top]