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.  doi: 10.1103/RevModPhys.74.47.  Google Scholar

[2]

M. Aldana, Boolean dynamics of networks with scale-free topology,, Physica D, 185 (2003), 45.  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, (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, (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, (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.   Google Scholar

[8]

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

[9]

A. Kaiser and T. Schreiber, Information transfer in continuous processes,, Physica D, 166 (2002), 43.  doi: 10.1016/S0167-2789(02)00432-3.  Google Scholar

[10]

F. Kepes, "Biological Networks,", $1^{st}$ edition, (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.  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).  doi: 10.1103/PhysRevE.69.066138.  Google Scholar

[13]

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

[14]

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

[15]

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

[16]

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

[17]

M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks,, Europhysics Letters, 84 (2008).  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.  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.  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).  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.   Google Scholar

[22]

M. Rubinov, O. Sporns, C. van Leeuwen and M. Breakspear, Symbiotic relationship between brain structure and dynamics,, BMC Neuroscience, 10 (2009).  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, (2004).   Google Scholar

[24]

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

[25]

S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology,, Physical Review E, 8 (2004), 180.   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.  doi: 10.1103/RevModPhys.74.47.  Google Scholar

[2]

M. Aldana, Boolean dynamics of networks with scale-free topology,, Physica D, 185 (2003), 45.  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, (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, (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, (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.   Google Scholar

[8]

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

[9]

A. Kaiser and T. Schreiber, Information transfer in continuous processes,, Physica D, 166 (2002), 43.  doi: 10.1016/S0167-2789(02)00432-3.  Google Scholar

[10]

F. Kepes, "Biological Networks,", $1^{st}$ edition, (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.  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).  doi: 10.1103/PhysRevE.69.066138.  Google Scholar

[13]

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

[14]

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

[15]

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

[16]

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

[17]

M. Piraveenan, M. Prokopenko and A. Y. Zomaya, Local assortativeness in scale-free networks,, Europhysics Letters, 84 (2008).  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.  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.  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).  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.   Google Scholar

[22]

M. Rubinov, O. Sporns, C. van Leeuwen and M. Breakspear, Symbiotic relationship between brain structure and dynamics,, BMC Neuroscience, 10 (2009).  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, (2004).   Google Scholar

[24]

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

[25]

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

[1]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[2]

Guillaume Cantin, M. A. Aziz-Alaoui. Dimension estimate of attractors for complex networks of reaction-diffusion systems applied to an ecological model. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020283
[3]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295
[4]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325
[5]

Xiaoxian Tang, Jie Wang. Bistability of sequestration networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1337-1357. doi: 10.3934/dcdsb.2020165
[6]

Wai-Ki Ching, Jia-Wen Gu, Harry Zheng. On correlated defaults and incomplete information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 889-908. doi: 10.3934/jimo.2020003
[7]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, 2021, 14 (1) : 77-88. doi: 10.3934/krm.2020049
[8]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033
[9]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[10]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020406
[11]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346
[12]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344
[13]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[14]

Pedro Aceves-Sanchez, Benjamin Aymard, Diane Peurichard, Pol Kennel, Anne Lorsignol, Franck Plouraboué, Louis Casteilla, Pierre Degond. A new model for the emergence of blood capillary networks. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021001
[15]

Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021001
[16]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[17]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054
[18]

Honglin Yang, Jiawu Peng. Coordinating a supply chain with demand information updating. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020181
[19]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[20]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016

2019 Impact Factor: 1.053

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences