×

zbMATH — the first resource for mathematics

Optimal partition and effective dynamics of complex networks. (English) Zbl 1205.68031
Summary: Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.

MSC:
68M10 Network design and communication in computer systems
37N99 Applications of dynamical systems
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
90B15 Stochastic network models in operations research
PDF BibTeX Cite
Full Text: DOI
References:
[1] Reviews of Modern Physics 74 pp 47– (2002) · Zbl 1205.82086
[2] IEEE TRANS PATTERN ANAL MACH INTELL 22 pp 888– (2000) · Zbl 05111961
[3] Girvan, PNAS 99 (12) pp 7821– (2002) · Zbl 1032.91716
[4] LECT NOTES COMPUT SCI 2346 pp 83– (2002)
[5] LECT NOTES COMPUT SCI 3243 pp 181– (2004)
[6] PHYS REV E 70 pp 056104– (2004)
[7] PHYS REV E 70 pp 025101– (2004)
[8] PHYS REV E 69 pp 066133– (2004)
[9] PHYS REV E 69 pp 026113– (2004)
[10] PNAS 101 (9) pp 2658– (2004)
[11] Reichardt, Physical Review Letters 93 (21) pp 218701– (2004)
[12] EUR. PHYS. J. B 38 pp 331– (2004)
[13] LECT NOTES COMPUT SCI 3038 pp 1062– (2004)
[14] PHYS REV E 72 pp 027104– (2005)
[15] Palla, Nature; Physical Science (London) 435 (7043) pp 814– (2005)
[16] PNAS 103 (23) pp 8577– (2006)
[17] IEEE TRANS PATTERN ANAL MACH INTELL 28 pp 1393– (2006) · Zbl 05112264
[18] COMMUN PURE APPL MATH 52 pp 1231– (1999) · Zbl 0933.65123
[19] Chorin, PNAS 97 (7) pp 2968– (2000) · Zbl 0968.60036
[20] MULTISCALE MODEL SIMULAT 1 pp 105– (2003) · Zbl 1064.65004
[21] COMBINATORICS PAUL ERDOS IS EIGHTY 2 pp 1– (1993)
[22] SIAM J NUMER ANAL 36 pp 491– (1999) · Zbl 0916.58021
[23] LECT NOTES COMP SCI ENG 4 pp 98– (1999)
[24] LINEAR ALG APPL 315 pp 39– (2000) · Zbl 0963.65008
[25] THEOR PROBAB APPL 11 pp 211– (1966) · Zbl 0168.16002
[26] J ANTHROP RES 33 pp 452– (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.