On congruity of nodes and assortative information content in complex networks

Mahendra Piraveenan; Mikhail Prokopenko; Albert Y. Zomaya; Mahendra Piraveenan; Mikhail Prokopenko; Albert Y. Zomaya

doi:10.3934/nhm.2012.7.441

Networks and Heterogeneous Media

2012, Volume 7, Issue 3: 441-461. doi: 10.3934/nhm.2012.7.441

Previous Article Next Article

On congruity of nodes and assortative information content in complex networks

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

Received: 01 December 2011 Revised: 01 June 2012
Primary: 91D30, 05C82, 90B18; Secondary: 92C42.

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.
- Complex networks,
- graph theory,
- assortativity,
- information content,
- congruity
Citation: Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks[J]. Networks and Heterogeneous Media, 2012, 7(3): 441-461. doi: 10.3934/nhm.2012.7.441

Related Papers:

Abstract

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.

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.

Reader Comments

Your name:*

Email:*
© 2012 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)