On congruity of nodes and assortative information content in complex networks

Previous Article
Identifying critical traffic jam areas with node centralities interference and robustness
NHM Home
This Issue
Next Article
Effects of topology on robustness in ecological bipartite networks

September 2012, 7(3): 441-461. doi: 10.3934/nhm.2012.7.441

On congruity of nodes and assortative information content in complex networks

Mahendra Piraveenan ^1, , Mikhail Prokopenko ^2, and Albert Y. Zomaya ^3,

1.	The Centre for Complex Systems Research, Project Management Graduate Programme, School of Civil Engineering, University of Sydney, NSW 2006, Australia
2.	CSIRO Information and Communications Technologies Centre, Locked Bag 17, North Ryde, NSW 1670, Australia
3.	The Centre for Distributed and High Performance Computing, School of Information Technologies, University of Sydney, NSW 2006, Australia

Received December 2011 Revised June 2012 Published October 2012

Abstract
Related Papers

Many distributed systems lend themselves to be modelled as networks, where nodes can have a range of attributes and properties based on which they may be classified. In this paper, we attempt the task of quantifying varying levels of similarity among nodes in a complex network over a period of time. We analyze how this similarity varies as nodes implement their functional logic and node states vary accordingly. We then use information theory to analyze how much Shannon information is conveyed by such a similarity measure, and how such information varies with time. We also propose node congruity as a measure to quantify the contribution of each node to the network's scalar assortativity. Finally, focussing on networks with binary states, we present algorithms (logic functions) which can be implemented in nodes to maximize or minimize scalar assortativity in a given network, and analyze the corresponding tendencies in information content.

Keywords: Complex networks, congruity., assortativity, information content, graph theory.

Mathematics Subject Classification: Primary: 91D30, 05C82, 90B18; Secondary: 92C4.

Citation: Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks. Networks and Heterogeneous Media, 2012, 7 (3) : 441-461. doi: 10.3934/nhm.2012.7.441

References:

[1]	R. Albert and A. L. Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics, 74 (2002), 47-97. doi: 10.1103/RevModPhys.74.47.
[2]	M. Aldana, Boolean dynamics of networks with scale-free topology, Physica D, 185 (2003), 45-66. doi: 10.1016/S0167-2789(03)00174-X.
[3]	U. Alon, "Introduction to Systems Biology: Design Principles of Biological Circuits," $1^{st}$ edition, Chapman and Hall, London, 2007.
[4]	D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman and S. H. Strogatz, Are randomly grown graphs really random, Physical Review E, 64 (2001). doi: 10.1103/PhysRevE.64.041902.
[5]	K. K. S. Chung, L. Hossain and J. Davis, Exploring sociocentric and egocentric approaches for social network analysis, in "KMAP 2005: Knowledge Management in Asia Pacific, Wellington, New Zealand," 2005.
[6]	S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of Networks: From Biological Nets to the Internet and WWW," $1^{st}$ edition, Oxford University Press, Oxford, 2003.
[7]	R. Guimera, M. Sales-Pardo and L. A. Amaral, Classes of complex networks defined by role-to-role connectivity profiles, Nature Physics, 3 (2007), 63-69.
[8]	B. H. Junker and F. Schreiber, "Analysis of Biological Networks (Wiley Series in Bioinformatics)," $1^{st}$ edition, Wiley-Interscience, 2008.
[9]	A. Kaiser and T. Schreiber, Information transfer in continuous processes, Physica D, 166 (2002), 43-62. doi: 10.1016/S0167-2789(02)00432-3.
[10]	F. Kepes, "Biological Networks," $1^{st}$ edition, World Scientific, Singapore, 2007.
[11]	S. Knock, A. McIntosh, O. Sporns, R. Ktter, P. Hagmann and V. Jirsa, The effects of physiologically plausible connectivity structure on local and global dynamics in large scale brain models, Journal of Neuroscience Methods, 183 (2009), 86-94. doi: 10.1016/j.jneumeth.2009.07.007.
[12]	A. Kraskov, H. Stögbauer and P. Grassberger, Estimating mutual information, Physical review E, 69 (2004), 066138. doi: 10.1103/PhysRevE.69.066138.
[13]	D. J. MacKay, "Information Theory, Inference, and Learning Algorithms," $1^{st}$ edition, Cambridge University Press, Cambridge, 2003.
[14]	M. E. J. Newman, Assortative mixing in networks, Physical Review Letters, 89 (2002), 208701. doi: 10.1103/PhysRevLett.89.208701.
[15]	M. E. J. Newman, Mixing patterns in networks, Physical Review E, 67 (2003), 026126. doi: 10.1103/PhysRevE.67.026126.
[16]	B. O. Palsson, "Systems Biology: Properties of Reconstructed Networks," $1^{st}$ edition, Cambridge University Press, Cambridge, 2006.
[17]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks, Europhysics Letters, 84 (2008), 28002. doi: 10.1209/0295-5075/84/28002.
[18]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortativeness and information in scale-free networks, European Physical Journal B, 67 (2009), 291-300. doi: 10.1140/epjb/e2008-00473-5.
[19]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortativity and growth of Internet, European Physical Journal B, 70 (2009), 275-285. doi: 10.1140/epjb/e2009-00219-y.
[20]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks-addendum, Europhysics Letters, 89 (2010), 49901. doi: 10.1209/0295-5075/89/49901.
[21]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortative mixing in directed biological networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9 (2012), 66-78.
[22]	M. Rubinov, O. Sporns, C. van Leeuwen and M. Breakspear, Symbiotic relationship between brain structure and dynamics, BMC Neuroscience, 10 (2009), 55. doi: 10.1186/1471-2202-10-55.
[23]	R. V. Sole and S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in "Lecture Notes in Physics" (eds. E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai), Springer, (2004), 650.
[24]	S. Zhou and R. J. Mondragón, Towards modelling the internet topology - the interactive growth model, Physical Review E, 67 (2003), 026126.
[25]	S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology, Physical Review E, 8 (2004), 180-182.

show all references

References:

[1]	R. Albert and A. L. Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics, 74 (2002), 47-97. doi: 10.1103/RevModPhys.74.47.
[2]	M. Aldana, Boolean dynamics of networks with scale-free topology, Physica D, 185 (2003), 45-66. doi: 10.1016/S0167-2789(03)00174-X.
[3]	U. Alon, "Introduction to Systems Biology: Design Principles of Biological Circuits," $1^{st}$ edition, Chapman and Hall, London, 2007.
[4]	D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman and S. H. Strogatz, Are randomly grown graphs really random, Physical Review E, 64 (2001). doi: 10.1103/PhysRevE.64.041902.
[5]	K. K. S. Chung, L. Hossain and J. Davis, Exploring sociocentric and egocentric approaches for social network analysis, in "KMAP 2005: Knowledge Management in Asia Pacific, Wellington, New Zealand," 2005.
[6]	S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of Networks: From Biological Nets to the Internet and WWW," $1^{st}$ edition, Oxford University Press, Oxford, 2003.
[7]	R. Guimera, M. Sales-Pardo and L. A. Amaral, Classes of complex networks defined by role-to-role connectivity profiles, Nature Physics, 3 (2007), 63-69.
[8]	B. H. Junker and F. Schreiber, "Analysis of Biological Networks (Wiley Series in Bioinformatics)," $1^{st}$ edition, Wiley-Interscience, 2008.
[9]	A. Kaiser and T. Schreiber, Information transfer in continuous processes, Physica D, 166 (2002), 43-62. doi: 10.1016/S0167-2789(02)00432-3.
[10]	F. Kepes, "Biological Networks," $1^{st}$ edition, World Scientific, Singapore, 2007.
[11]	S. Knock, A. McIntosh, O. Sporns, R. Ktter, P. Hagmann and V. Jirsa, The effects of physiologically plausible connectivity structure on local and global dynamics in large scale brain models, Journal of Neuroscience Methods, 183 (2009), 86-94. doi: 10.1016/j.jneumeth.2009.07.007.
[12]	A. Kraskov, H. Stögbauer and P. Grassberger, Estimating mutual information, Physical review E, 69 (2004), 066138. doi: 10.1103/PhysRevE.69.066138.
[13]	D. J. MacKay, "Information Theory, Inference, and Learning Algorithms," $1^{st}$ edition, Cambridge University Press, Cambridge, 2003.
[14]	M. E. J. Newman, Assortative mixing in networks, Physical Review Letters, 89 (2002), 208701. doi: 10.1103/PhysRevLett.89.208701.
[15]	M. E. J. Newman, Mixing patterns in networks, Physical Review E, 67 (2003), 026126. doi: 10.1103/PhysRevE.67.026126.
[16]	B. O. Palsson, "Systems Biology: Properties of Reconstructed Networks," $1^{st}$ edition, Cambridge University Press, Cambridge, 2006.
[17]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks, Europhysics Letters, 84 (2008), 28002. doi: 10.1209/0295-5075/84/28002.
[18]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortativeness and information in scale-free networks, European Physical Journal B, 67 (2009), 291-300. doi: 10.1140/epjb/e2008-00473-5.
[19]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortativity and growth of Internet, European Physical Journal B, 70 (2009), 275-285. doi: 10.1140/epjb/e2009-00219-y.
[20]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks-addendum, Europhysics Letters, 89 (2010), 49901. doi: 10.1209/0295-5075/89/49901.
[21]	M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Assortative mixing in directed biological networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9 (2012), 66-78.
[22]	M. Rubinov, O. Sporns, C. van Leeuwen and M. Breakspear, Symbiotic relationship between brain structure and dynamics, BMC Neuroscience, 10 (2009), 55. doi: 10.1186/1471-2202-10-55.
[23]	R. V. Sole and S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in "Lecture Notes in Physics" (eds. E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai), Springer, (2004), 650.
[24]	S. Zhou and R. J. Mondragón, Towards modelling the internet topology - the interactive growth model, Physical Review E, 67 (2003), 026126.
[25]	S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology, Physical Review E, 8 (2004), 180-182.

[1]	Christian Bläsche, Shawn Means, Carlo R. Laing. Degree assortativity in networks of spiking neurons. Journal of Computational Dynamics, 2020, 7 (2) : 401-423. doi: 10.3934/jcd.2020016
[2]	Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks and Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295
[3]	M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201
[4]	C. Bonanno. The algorithmic information content for randomly perturbed systems. Discrete and Continuous Dynamical Systems - B, 2004, 4 (4) : 921-934. doi: 10.3934/dcdsb.2004.4.921
[5]	H. T. Banks, John E. Banks, R. A. Everett, John D. Stark. An adaptive feedback methodology for determining information content in stable population studies. Mathematical Biosciences & Engineering, 2016, 13 (4) : 653-671. doi: 10.3934/mbe.2016013
[6]	Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019
[7]	Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295
[8]	Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071
[9]	Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393
[10]	F. S. Vannucchi, S. Boccaletti. Chaotic spreading of epidemics in complex networks of excitable units. Mathematical Biosciences & Engineering, 2004, 1 (1) : 49-55. doi: 10.3934/mbe.2004.1.49
[11]	Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292
[12]	Xiwei Liu, Tianping Chen, Wenlian Lu. Cluster synchronization for linearly coupled complex networks. Journal of Industrial and Management Optimization, 2011, 7 (1) : 87-101. doi: 10.3934/jimo.2011.7.87
[13]	Antonio Ambrosetti, Massimiliano Berti. Applications of critical point theory to homoclinics and complex dynamics. Conference Publications, 1998, 1998 (Special) : 72-78. doi: 10.3934/proc.1998.1998.72
[14]	Karim El Laithy, Martin Bogdan. Synaptic energy drives the information processing mechanisms in spiking neural networks. Mathematical Biosciences & Engineering, 2014, 11 (2) : 233-256. doi: 10.3934/mbe.2014.11.233
[15]	Shui-Nee Chow, Xiaojing Ye, Hongyuan Zha, Haomin Zhou. Influence prediction for continuous-time information propagation on networks. Networks and Heterogeneous Media, 2018, 13 (4) : 567-583. doi: 10.3934/nhm.2018026
[16]	Heman Shakeri, Faryad Darabi Sahneh, Caterina Scoglio, Pietro Poggi-Corradini, Victor M. Preciado. Optimal information dissemination strategy to promote preventive behaviors in multilayer epidemic networks. Mathematical Biosciences & Engineering, 2015, 12 (3) : 609-623. doi: 10.3934/mbe.2015.12.609
[17]	Jingli Ren, Dandan Zhu, Haiyan Wang. Spreading-vanishing dichotomy in information diffusion in online social networks with intervention. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1843-1865. doi: 10.3934/dcdsb.2018240
[18]	Robert Carlson. Spectral theory for nonconservative transmission line networks. Networks and Heterogeneous Media, 2011, 6 (2) : 257-277. doi: 10.3934/nhm.2011.6.257
[19]	Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic and Related Models, 2017, 10 (1) : 1-32. doi: 10.3934/krm.2017001
[20]	Massimiliano Zanin, Ernestina Menasalvas, Pedro A. C. Sousa, Stefano Boccaletti. Preprocessing and analyzing genetic data with complex networks: An application to Obstructive Nephropathy. Networks and Heterogeneous Media, 2012, 7 (3) : 473-481. doi: 10.3934/nhm.2012.7.473

2020 Impact Factor: 1.213

Tools

Metrics

Other articles
by authors

on AIMS
Mahendra Piraveenan Mikhail Prokopenko Albert Y. Zomaya
on Google Scholar
Mahendra Piraveenan Mikhail Prokopenko Albert Y. Zomaya

[Back to Top]