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

* Corresponding author: Pietro Poggi-Corradini

Received  January 2017 Revised  March 2018 Published  January 2019 Early access  June 2018

Fund Project: The authors are supported by NSF n. 1515810.

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.

Citation: Nathan Albin, Nethali Fernando, Pietro Poggi-Corradini. Modulus metrics on networks. Discrete and 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.

[2]

N. AlbinM. BrunnerR. PerezP. 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.

[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. DingJ. 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].

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

[2]

N. AlbinM. BrunnerR. PerezP. 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.

[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. DingJ. 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].

[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 1.  The path graph $P_3$ on three nodes
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 5.  The complete graph $K_N$ and the extremal density $\rho^*$ for $\Gamma(a, b)$
Figure 6.  The square graph
Figure 7.  Eigenvalues of $M$ as $\beta$ varies, given $\alpha = 1$
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 and 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 and 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 and 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 and 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]

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

[8]

Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks and Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143

[9]

Carlos A. Berenstein and Alain Yger. Residues and effective Nullstellensatz. Electronic Research Announcements, 1996, 2: 82-91.

[10]

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

[11]

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

[12]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[13]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[14]

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

[15]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[16]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075

[17]

Piotr Bajger, Mariusz Bodzioch, Urszula Foryś. Singularity of controls in a simple model of acquired chemotherapy resistance. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2039-2052. doi: 10.3934/dcdsb.2019083

[18]

Urszula Ledzewicz, Heinz Schättler. Drug resistance in cancer chemotherapy as an optimal control problem. Discrete and Continuous Dynamical Systems - B, 2006, 6 (1) : 129-150. doi: 10.3934/dcdsb.2006.6.129

[19]

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

[20]

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

2020 Impact Factor: 1.327

Metrics

  • PDF downloads (223)
  • HTML views (424)
  • Cited by (0)

[Back to Top]