Electrical networks with prescribed current and applications to random walks on graphs

Christina Knox; Amir Moradifam

doi:10.3934/ipi.2019018

Article Contents

2019, Volume 13, Issue 2: 353-375. Doi: 10.3934/ipi.2019018

This issue Previous Article Propagation of boundary-induced discontinuity in stationary radiative transfer and its application to the optical tomography Next Article An inverse obstacle problem for the wave equation in a finite time domain

Electrical networks with prescribed current and applications to random walks on graphs

Christina Knox and
Amir Moradifam^,

University of California, Riverside, Riverside, CA 92501, USA

^* Corresponding author: Amir Moradifam
^* Corresponding author: Amir Moradifam

Received: June 2018

Revised: September 2018

Published: April 2019

The second author is supported by NSF grant DMS-1715850.

Abstract / Introduction Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

In this paper we study Current Density Impedance Imaging (CDII) on Electrical Networks. The inverse problem is to determine the conductivity matrix of an electrical network from the prescribed knowledge of the magnitude of the induced current along the edges coupled with the imposed voltage or injected current on the boundary nodes. This problem leads to a weighted $ l^1 $ minimization problem for the corresponding voltage potential. We also investigate the problem of determining the transition probabilities of random walks on graphs from the prescribed expected net number of times the walker passes along the edges of the graph. Convergent numerical algorithms for solving such problems are also presented. Our results can be utilized in the design of electrical networks when certain current flow on the network is desired as well as the design of random walk models on graphs when the expected net number of the times the walker passes along the edges is prescribed. We also show that a mass preserving flow $ J = (J_{ij}) $ on a network can be uniquely recovered from the knowledge of $ |J| = (|J_{ij}|) $ and the flux of the flow on the boundary nodes, where $ J_{ij} $ is the flow from node $ i $ to node $ j $ and $ J_{ij} = -J_{ji} $, and discuss its potential application in cryptography.

Keywords:

Mathematics Subject Classification: Primary: 35R30, 94C99; Secondary: 49N45, 05C81.

Citation:

Full Text(HTML)

Table 1. Numerical errors for algorithm 1 on 100 node graph with 1121 edges

Tolerance	Relative L2 Error	Number of Iterations	Elapsed Time(s)
$ 10^{-3} $	1.2171$ \times 10^{-3} $	16	0.069309
$ 10^{-4} $	1.3160$ \times 10^{-4} $	22	0.102846
$ 10^{-5} $	1.4494$ \times 10^{-5} $	92	0.358250
$ 10^{-6} $	1.3615$ \times 10^{-6} $	133	0.405979

| Show Table

DownLoad: CSV

Table 2. Numerical errors for algorithm 2 on 100 node graph with 1121 edges

Tolerance	Relative L2 Error	Number of Iterations	Elapsed Time(s)
$ 10^{-2} $	1.3069$ \times 10^{-3} $	7	0.055400
$ 10^{-3} $	1.3908$ \times 10^{-4} $	9	0.071342
$ 10^{-4} $	1.0235$ \times 10^{-5} $	12	0.086956
$ 10^{-5} $	1.1987$ \times 10^{-6} $	24	0.147310

| Show Table

DownLoad: CSV

Table 3. Average Number of Iterations

Tolerance	Algorithm 1	Algorithm 2
$ 10^{-3} $	21.175	15.918
$ 10^{-4} $	46.097	18.905
$ 10^{-5} $	111.847	23.486
$ 10^{-6} $	227.624	32.846

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	J.-F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Modeling & Simulation, 8 (2009), 337-369. doi: 10.1137/090753504.
[2]	R. M. Christley, G. Pinchbeck, R. Bowers, D. Clancy, N. French, R. Bennett and J. Turner, Infection in social networks: using network analysis to identify high-risk individuals, American Journal of Epidemiology, 162 (2005), 1024-1031. doi: 10.1093/aje/kwi308.
[3]	S.-Y. Chung and C. A. Berenstein, $\omega$-harmonic functions and inverse conductivity problems on networks, SIAM Journal on Applied Mathematics, 65 (2005), 1200-1226. doi: 10.1137/S0036139903432743.
[4]	C. Cooper, R. Elsasser, H. Ono and T. Radzik, Coalescing random walks and voting on connected graphs, SIAM Journal on Discrete Mathematics, 27 (2013), 1748-1758. doi: 10.1137/120900368.
[5]	E. B. Curtis and J. A. Morrow, Inverse Problems for Electrical Networks, vol. 13, World Scientific, 2000.
[6]	P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, Mathematical Association of America, 1984.
[7]	M. Draief and A. Ganesh, A random walk model for infection on graphs: Spread of epidemics & rumours with mobile agents, Discrete Event Dynamic Systems, 21 (2011), 41-61. doi: 10.1007/s10626-010-0092-5.
[8]	J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318. doi: 10.1007/BF01581204.
[9]	I. Ekeland and R. Temam, Convex Analysis and Variational Problems, SIAM, 1999. doi: 10.1137/1.9781611971088.
[10]	E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split bregman, CAM report, 9 (2009), 31.
[11]	E. F. Fama, Random walks in stock market prices, Financial Analysts Journal, 51 (1995), 75-80.
[12]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary Value Problems, Studies in Mathematics and its Applications (eds. F. M. and G. R.), vol. 15, 1983, chapter 9,299–331.
[13]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & Mathematics with Applications, 2 (1976), 17-40.
[14]	R. Glowinski and A. Marroco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Revue Française D'automatique, Informatique, Recherche Opérationnelle. Analyse Numérique, 9 (1975), 41–76.
[15]	T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[16]	P. R. Halmos, Finite-dimensional Vector Spaces, Springer-Verlag, New York-Heidelberg, 1974.
[17]	K. F. Hasanov, A. W. Ma, R. S. Yoon, A. I. Nachman and M. Joy, A new approach to current density impedance imaging, in Engineering in Medicine and Biology Society, 2004. IEMBS'04. 26th Annual International Conference of the IEEE, vol. 1, IEEE, 2004, 1321–1324.
[18]	M. R. Henzinger, A. Heydon, M. Mitzenmacher and M. Najork, Measuring index quality using random walks on the web, Computer Networks, 31 (1999), 1291-1303.
[19]	N. Hoell, A. Moradifam and A. Nachman, Current density impedance imaging of an anisotropic conductivity in a known conformal class, SIAM Journal on Mathematical Analysis, 46 (2014), 1820-1842. doi: 10.1137/130911524.
[20]	R. L. Jerrard, A. Moradifam and A. I. Nachman, Existence and uniqueness of minimizers of general least gradient problems, J. Reine Angew. Math., 734 (2018), 71-97. doi: 10.1515/crelle-2014-0151.
[21]	M. Joy, G. Scott and M. Henkelman, In vivo detection of applied electric currents by magnetic resonance imaging, Magnetic Resonance Imaging, 7 (1989), 89-94.
[22]	S. Kim, O. Kwon, J. K. Seo and J.-R. Yoon, On a nonlinear partial differential equation arising in magnetic resonance electrical impedance tomography, SIAM Journal on Mathematical Analysis, 34 (2002), 511-526.
[23]	Y. J. Kim, O. Kwon, J. K. Seo and E. J. Woo, Uniqueness and convergence of conductivity image reconstruction in magnetic resonance electrical impedance tomography, Inverse Problems, 19 (2003), 1213-1225. doi: 10.1088/0266-5611/19/5/312.
[24]	O. Kwon, J.-Y. Lee and J.-R. Yoon, Equipotential line method for magnetic resonance electrical impedance tomography, Inverse Problems, 18 (2002), 1089-1100. doi: 10.1088/0266-5611/18/4/310.
[25]	L. Lovász, Random walks on graphs, Combinatorics, Paul Erdos is Eighty, 2 (1993), 1-46.
[26]	A. Moradifam, Existence and structure of minimizers of least gradient problems, Indiana University Mathematics Journal, 67 (2018), 1025-1037. doi: 10.1512/iumj.2018.67.7360.
[27]	A. Moradifam and A. Nachman, Convergence of the alternating split Bregman algorithm in infinite-dimensional Hilbert spaces.
[28]	A. Moradifam, A. Nachman and A. Tamasan, Conductivity imaging from one interior measurement in the presence of perfectly conducting and insulating inclusions, SIAM Journal on Mathematical Analysis, 44 (2012), 3969-3990. doi: 10.1137/120866701.
[29]	A. Moradifam, A. Nachman and A. Timonov, A convergent algorithm for the hybrid problem of reconstructing conductivity from minimal interior data, Inverse Problems, 28 (2012), 084003, 23PP. doi: 10.1088/0266-5611/28/8/084003.
[30]	A. Nachman, A. Tamasan and A. Timonov, Current density impedance imaging, in Tomography and Inverse Transport Theory, vol. 559, Amer. Math. Soc. Providence, RI, 2011,135–149. doi: 10.1090/conm/559/11076.
[31]	A. Nachman, A. Tamasan and A. Timonov, Conductivity imaging with a single measurement of boundary and interior data, Inverse Problems, 23 (2007), 2551-2563. doi: 10.1088/0266-5611/23/6/017.
[32]	A. Nachman, A. Tamasan and A. Timonov, Recovering the conductivity from a single measurement of interior data, Inverse Problems, 25 (2009), 035014, 16PP. doi: 10.1088/0266-5611/25/3/035014.
[33]	A. Nachman, A. Tamasan and A. Timonov, Reconstruction of planar conductivities in subdomains from incomplete data, SIAM Journal on Applied Mathematics, 70 (2010), 3342-3362. doi: 10.1137/10079241X.
[34]	A. Nachman, A. Tamasan and J. Veras, A weighted minimum gradient problem with complete electrode model boundary conditions for conductivity imaging, SIAM Journal on Applied Mathematics, 76 (2016), 1321-1343. doi: 10.1137/15M100897X.
[35]	S. Ribas, B. Ribeiro-Neto, R. L. Santos, E. de Souza e Silva, A. Ueda and N. Ziviani, Random walks on the reputation graph, in Proceedings of the 2015 International Conference on The Theory of Information Retrieval, ACM, 2015,181–190.
[36]	P. Sarkar and A. W. Moore, Random walks in social networks and their applications: A survey, in Social Network Data Analytics, Springer, 2011, 43–77. doi: 10.1007/978-1-4419-8462-3_3.
[37]	S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, in International Conference on Scale Space and Variational Methods in Computer Vision, Springer, 2009,464–476.
[38]	S. Setzer, Operator splittings, Bregman methods and frame shrinkage in image processing, International Journal of Computer Vision, 92 (2011), 265-280. doi: 10.1007/s11263-010-0357-3.
[39]	A. Skogseid and V. Fasano, Statistical Mechanics and Random Walks: Principles, Processes, and Applications, Nova Science Publishers, 2012.
[40]	M. E. Yildiz, R. Pagliari, A. Ozdaglar and A. Scaglione, Voting models in random networks, in Information Theory and Applications Workshop (ITA), 2010, Institute of Electrical and Electronics Engineers, 2010, 1–7. doi: 10.1109/ITA.2010.5454090.