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 & 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. 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.  Google Scholar

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

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

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

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

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

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

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

[12]

D. A. Spielman, Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.), 54 (2017), 45-61.  doi: 10.1090/bull/1557.  Google Scholar

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

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

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

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

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

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

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

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

[12]

D. A. Spielman, Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.), 54 (2017), 45-61.  doi: 10.1090/bull/1557.  Google Scholar

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

Metrics

  • PDF downloads (140)
  • HTML views (421)
  • Cited by (0)

[Back to Top]