American Institute of Mathematical Sciences

Advanced
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

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 & 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.  Google Scholar

[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.  Google Scholar

[3]

U. Alon, "Introduction to Systems Biology: Design Principles of Biological Circuits," $1^{st}$ edition, Chapman and Hall, London, 2007.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

B. H. Junker and F. Schreiber, "Analysis of Biological Networks (Wiley Series in Bioinformatics)," $1^{st}$ edition, Wiley-Interscience, 2008. Google Scholar

[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.  Google Scholar

[10]

F. Kepes, "Biological Networks," $1^{st}$ edition, World Scientific, Singapore, 2007. Google Scholar

[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.  Google Scholar

[12]

A. Kraskov, H. Stögbauer and P. Grassberger, Estimating mutual information, Physical review E, 69 (2004), 066138. doi: 10.1103/PhysRevE.69.066138.  Google Scholar

[13]

D. J. MacKay, "Information Theory, Inference, and Learning Algorithms," $1^{st}$ edition, Cambridge University Press, Cambridge, 2003.  Google Scholar

[14]

M. E. J. Newman, Assortative mixing in networks, Physical Review Letters, 89 (2002), 208701. doi: 10.1103/PhysRevLett.89.208701.  Google Scholar

[15]

M. E. J. Newman, Mixing patterns in networks, Physical Review E, 67 (2003), 026126. doi: 10.1103/PhysRevE.67.026126.  Google Scholar

[16]

B. O. Palsson, "Systems Biology: Properties of Reconstructed Networks," $1^{st}$ edition, Cambridge University Press, Cambridge, 2006. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

S. Zhou and R. J. Mondragón, Towards modelling the internet topology - the interactive growth model, Physical Review E, 67 (2003), 026126. Google Scholar

[25]

S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology, Physical Review E, 8 (2004), 180-182. Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

U. Alon, "Introduction to Systems Biology: Design Principles of Biological Circuits," $1^{st}$ edition, Chapman and Hall, London, 2007.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

B. H. Junker and F. Schreiber, "Analysis of Biological Networks (Wiley Series in Bioinformatics)," $1^{st}$ edition, Wiley-Interscience, 2008. Google Scholar

[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.  Google Scholar

[10]

F. Kepes, "Biological Networks," $1^{st}$ edition, World Scientific, Singapore, 2007. Google Scholar

[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.  Google Scholar

[12]

A. Kraskov, H. Stögbauer and P. Grassberger, Estimating mutual information, Physical review E, 69 (2004), 066138. doi: 10.1103/PhysRevE.69.066138.  Google Scholar

[13]

D. J. MacKay, "Information Theory, Inference, and Learning Algorithms," $1^{st}$ edition, Cambridge University Press, Cambridge, 2003.  Google Scholar

[14]

M. E. J. Newman, Assortative mixing in networks, Physical Review Letters, 89 (2002), 208701. doi: 10.1103/PhysRevLett.89.208701.  Google Scholar

[15]

M. E. J. Newman, Mixing patterns in networks, Physical Review E, 67 (2003), 026126. doi: 10.1103/PhysRevE.67.026126.  Google Scholar

[16]

B. O. Palsson, "Systems Biology: Properties of Reconstructed Networks," $1^{st}$ edition, Cambridge University Press, Cambridge, 2006. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

S. Zhou and R. J. Mondragón, Towards modelling the internet topology - the interactive growth model, Physical Review E, 67 (2003), 026126. Google Scholar

[25]

S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology, Physical Review E, 8 (2004), 180-182. Google Scholar

[1]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295
[2]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201
[3]

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

C. Bonanno. The algorithmic information content for randomly perturbed systems. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Heterogeneous Media, 2011, 6 (2) : 257-277. doi: 10.3934/nhm.2011.6.257
[19]

Maya Mincheva, Gheorghe Craciun. Graph-theoretic conditions for zero-eigenvalue Turing instability in general chemical reaction networks. Mathematical Biosciences & Engineering, 2013, 10 (4) : 1207-1226. doi: 10.3934/mbe.2013.10.1207
[20]

A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial & Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (23)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences