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

Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349

[2]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[3]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445

[4]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442

[5]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (90)
  • HTML views (394)
  • Cited by (0)

[Back to Top]