Towards structural network analysis

Matthias Dehmer ; Marina Popovscaia

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2010), pp. 3-22.

Résumé

Structural network analysis is an intricate problem. In fact, the majority of techniques that have been developed so far are only applicable to investigate deterministic network models. This gives rise to develop novel graph-theoretical methods for applying them to more complex graphs and especially to statistically inferred networks. In this regard, we review methods for analyzing complex networks structurally putting the special emphasis on network partitioning and quantifying network complexity. Both areas are of general importance in structural graph theory as well as useful for exploring biological networks.

Bibliographie

[1] Allen E. B., “Measuring graph abstractions of software: An information-theory approach”, Proceedings of the 8-th International Symposium on Software Metrics, IEEE Computer Society, 2002, 182

[2] Balaban A. T., “Highly discriminating distance-based topological index”, Chem. Phys. Lett., 89 (1982), 399–404 | DOI | MR

[3] Balaban A. T., Balaban T. S., “New vertex invariants and topological indices of chemical graphs based on information on distances”, J. Math. Chem., 8 (1991), 383–397 | DOI | MR

[4] Balaban A. T., Ivanciuc O., “Historical development of topological indices”, Topological Indices and Related Descriptors in QSAR and QSPAR, eds. Balaban A. T., Devillers J., Gordon and Breach Science Publishers, Amsterdam, The Netherlands, 1999, 21–57

[5] Bang-Jensen J., Gutin G., Digraphs. Theory, Algorithms and Applications, Springer, London–Berlin–Heidelberg, 2002 | MR | Zbl

[6] Basak S. C., “Information-theoretic indices of neighborhood complexity and their applications”, Topological Indices and Related Descriptors in QSAR and QSPAR, eds. Balaban A. T., Devillers J., Gordon and Breach Science Publishers, Amsterdam, The Netherlands, 1999, 563–595

[7] Basak S. C., Balaban A. T., Grunwald G. D., Gute B. D., “Topological indices: Their nature and mutual relatedness”, J. Chem. Inf. Comput. Sci., 40 (2000), 891–898 | DOI

[8] Basak S. C., Magnuson V. R., “Molecular topology and narcosis”, Arzeim.-Forsch./Drug Design, 33:1 (1983), 501–503

[9] Bertz S. H., Herndon W. C., “The similarity of graphs and molecules”, Artificial Intelligence Applications in Chemistry, American Chemical Society, 1986, Chapter 15, 169–175

[10] Bertz S. H., Wright W. F., “The graph theory approach to synthetic analysis: Definition and application of molecular complexity and synthetic complexity”, Graph Theory Notes of New York, 35 (1998), 32–48 | MR

[11] Boccaletti S., Latora V., Moreno Y., Chavez M., Hwang D.-U., “Complex networks: Structure and dynamics”, Physics Reports, 424:4–5 (2006), 175–308 | DOI | MR

[12] Bock H. H., Automatische Klassifikation. Theoretische und praktische Methoden zur Gruppierung und Strukturierung von Daten, Studia Mathematica. Vandenhoeck Ruprecht, Göttingen, 1974 | MR | Zbl

[13] Bonchev D., Information Theoretic Indices for Characterization of Chemical Structures, Research Studies Press, Chichester, 1983

[14] Bonchev D., “Overall connectivities and topological complexities: A new powerful tool for QSPR/QSAR”, J. Chem. Inf. Comput. Sci., 40:4 (2000), 934–941 | DOI

[15] Bonchev D., “The overall Wiener index – a new tool for characterization of molecular topology”, J. Chem. Inf. Comput. Sci., 41 (2001), 582–592 | DOI

[16] Bonchev D., “The overall topological complexity indices”, Advances in Computational Methods in Science and Engineering, 4B, eds. Simos T., Maroulis G., VSP Publications, 2005, 1554–1557

[17] Bonchev D., Rouvray D. H., Complexity in Chemistry, Biology, and Ecology, Mathematical and Computational Chemistry, Springer, New York, NY, USA, 2005 | MR | Zbl

[18] Bonchev D., Trinajstić N., “Information theory, distance matrix and molecular branching”, J. Chem. Phys., 67 (1977), 4517–4533 | DOI

[19] Bonchev D., Trinajstić N., “Overall molecular descriptors. 3. Overall Zagreb indices”, SAR QSAR Environ. Res., 12 (2001), 213–236 | DOI

[20] Bosák J., Decompositions of Graphs, Mathematics and its Applications, Springer, 1990 | MR

[21] Brandstädt A., Le V. B., Sprinrad J. P., Graph Classes. A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999 | MR

[22] Broere I., Hajnal P., Mihók P., “Partition problems and kernels of graphs”, Discussiones Mathematicae Graph Theory, 17 (1997), 311–313 | DOI | MR | Zbl

[23] Calinescu A., Efstathiou J., Sivadasan S., Schirn J., Huaccho Huatuco L., “Complexity in manufacturing: an information theoretic approach”, Proceedings of the International Conference on Complex Systems and Complexity in Manufacturing, 2000, 30–44

[24] Causton H. C., Brazma A.,Quackenbush J., Microarray Gene Expression Data Analysis, Blackwell Publishers, 2003

[25] Chan P., Schlag M., Zien J., “Spectral $k$-way ratio cut partitioning”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13 (1994), 1088–1096 | DOI

[26] Cristianini N., Shawe-Taylor J., An Introduction to Support Vector Machines, Cambridge University Press, Cambridge, UK, 2000

[27] Dancoff S. M., Quastler H., “Information content and error rate of living things”, Essays on the Use of Information Theory in Biology, ed. Quastler H., University of Illinois Press, 1953, 263–274

[28] Dehmer M., “Information-theoretic concepts for the analysis of complex networks”, Appl. Artif. Intell., 22:7–8 (2008), 684–706 | DOI

[29] Dehmer M., “A novel method for measuring the structural information content of networks”, Cybernetics and Systems, 39 (2008), 825–843 | DOI

[30] Dehmer M., Structural Analysis of Complex Networks, Birkhäuser, Boston; Springer, Basel, 2010 | MR

[31] Dehmer M., Emmert-Streib F., Analysis of Complex Networks: From Biology to Linguistics, Wiley VCH, Weinheim, Germany, 2009 | MR | Zbl

[32] Dehmer M., Varmuza K., Borgert S., Emmert-Streib F., “On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures”, J. Chem. Inf. Model., 49 (2009), 1655–1663 | DOI

[33] Devillers J., Balaban A. T., Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach Science Publishers, Amsterdam, The Netherlands, 1999

[34] Dhillon I. S., Guan Y., Kulis B., “Weighted graph cuts without eigenvectors: a multilevel approach”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (2007), 1944–1957 | DOI | MR

[35] Diao Y., Lia M., Fenga Z., Yina J., Pana Y., “The community structure of human cellular signaling network”, Journal of Theoretical Biology, 247 (2007), 608–615 | DOI | MR

[36] Diudea M. V., Gutman I., Jäntschi L., Molecular Topology, Nova Publishing, New York, NY, USA, 2001

[37] Dorogovtsev S. N., Mendes J. F. F., Evolution of Networks. From Biological Networks to the Internet and WWW, Oxford University Press, 2003 | MR | Zbl

[38] Emmert-Streib F., Dehmer M., Analysis of Microarray Data: A Network-Based Approach, Wiley-VCH, 2008

[39] Emmert-Streib F., Dehmer M., Information Theory and Statistical Learning, Springer, New York, USA, 2008

[40] Emmert-Streib F., Dehmer M., “Information processing in the transcriptional regulatory network of yeast: Functional robustness”, BMC Syst. Biol., 3:35 (2009) | Zbl

[41] Erdös P., Rényi P., “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl, 5 (1960), 17–61 | MR | Zbl

[42] Felsenstein J., “Coalescents, phylogenies, and likelihoods”, Biological Bulletin, 196 (1999), 343–344 | DOI

[43] Fiduccia C. M., Mattheyses R. M., “A linear-time heuristic for improving network partitions”, Proceedings of the 19-th Design Automation Conference, 1982, 241–247

[44] Flake G. W., Lawrence S. R., Giles C. L., Coetzee F. M., “Self-organization and identification of web communities”, IEEE Computer, 35 (2002), 66–71 | DOI

[45] Frizelle G., Woodcock E., “Measuring complexity as an aid to developing operational strategy”, International Journal of Operations Production Management, 15 (1995), 26–39 | DOI

[46] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences, W. H. Freeman, 1979 | MR | Zbl

[47] Gasteiger J., Engel T., Chemoinformatics – A Textbook, Wiley VCH, Weinheim, Germany, 2003

[48] Girvan M., Newman M. E. J., “Community structure in social and biological networks”, PNAS, 99 (2002), 7821–7826 | DOI | MR | Zbl

[49] Gleiser P. M., Danon L., “Community structure in jazz”, Advances in complex systems, 6:4 (2003), 565–574 | DOI

[50] Godsil C., Royle G., Algebraic Graph Theory, Graduate Texts in Mathematics, Academic Press, 2001 | DOI | MR

[51] Golub G. H., Van Loan C. F., Matrix Computations, John Hopkins University Press, Baltimore, USA, 1996 | MR | Zbl

[52] Gregory S., “An algorithm to find overlapping community structure in networks”, Proceedings of 11th European conference on principles and practice of knowledge discovery in databases, PKDD' 07, 2007, 91–102

[53] Gutman I., Randić M., “Algebraic characterization of skeletal branching”, Chemical Physics Letters, 47:1 (1977), 15–17 | DOI

[54] Harary F., Graph Theory, Addison Wesley Publishing Company, Reading, MA, USA, 1969 | MR | Zbl

[55] Hirata H., Ulanowicz R. E., “Information theoretical analysis of ecological networks”, Int. J. Syst. Sci., 15 (1984), 261–270 | DOI | Zbl

[56] Holme P., Huss M., Jeong H., “Subnetwork hierarchies of biochemical pathways”, Bioinformatics, 19 (2003), 532–538 | DOI

[57] Huber W., Carey V., Long L., Falcon S., Gentleman R., “Graphs in molecular biology”, BMC Bioinformatics, 8, Suppl 6:S8 (2007)

[58] Jungnickel D., Graphs, networks and algorithms, Springer-Verlag, 2005 | MR | Zbl

[59] Junker B. H., Schreiber F., Analysis of biological networks, Wiley-Interscience, 2008

[60] Karypis G., Kumar V., “A fast and high quality multilevel scheme for partitioning irregular graphs”, SIAM Journal on Scientific Computing, 20 (1999), 359–392 | DOI | MR | Zbl

[61] Kernighan B. W., Lin S., “An efficient heuristic procedure for partitioning graphs”, Bell Systems Technical Journal, 49 (1970), 291–307 | DOI | Zbl

[62] Kim J., Wilhelm T., “What is a complex graph?”, Physica A, 387 (2008), 2637–2652 | DOI | MR

[63] Konstantinova E. V., “On some applications of information indices in chemical graph theory”, General Theory of Information Transfer and Combinatorics, Lecture Notes of Computer Science, 4123, eds. Ahlswede R., Bäumer L., Cai N., Aydinian H., Blinovsky V., Deppe C., Mashurian H., Springer, 2006, 831–852 | DOI | MR | Zbl

[64] Konstantinova E. V., Paleev A. A., “Sensitivity of topological indices of polycyclic graphs”, Vychisl. Sistemy, 136 (1990), 38–48 (in Russian) | MR | Zbl

[65] Konstantinova E. V., Skorobogatov V. A., Vidyuk M. V., “Applications of information theory in chemical graph theory”, Indian Journal of Chemistry, 42 (2002), 1227–1240

[66] Körner J., “Coding of an information source having ambiguous alphabet and the entropy of graphs”, Transactions of the 6-th Prague Conference on Information Theory, 1973, 411–425 | MR | Zbl

[67] Lauritzen S. L., Graphical Models, Oxford Statistical Science Series, Oxford University Press, 1996 | MR

[68] Linshitz H., “The information content of a battery cell”, Essays on the Use of Information Theory in Biology, ed. Quastler H., University of Illinois Press, Urbana, IL, USA, 1953

[69] Mazurie A., Bonchev D., Schwikowski B., Buck G. A., “Phylogenetic distances are encoded in networks of interacting pathways”, Bioinformatics, 24:22 (2008), 2579–2585 | DOI

[70] McCaskill J. S., “The equilibrium partition function and base pair binding probabilities for RNA secondary structure”, Biopolymers, 29 (1990), 1105–1119 | DOI

[71] Mehler A., “A Quantitative Graph Model of Social Ontologies by Example of Wikipedia”, Towards an Information Theory of Complex Networks: Statistical Methods and Applications, eds. Dehmer H., Emmert-Streib F., Birkhäuser, Boston/Basel, 2010 (to appear) | MR

[72] Minoli D., “Combinatorial graph complexity”, Atti. Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat., 59 (1975), 651–661 | MR

[73] Morowitz H., “Some order-disorder considerations in living systems”, Bull. Math. Biophys., 17 (1953), 81–86 | DOI

[74] Mowshowitz A., “Entropy and the complexity of the graphs I: An index of the relative complexity of a graph”, Bull. Math. Biophys., 30 (1968), 175–204 | DOI | MR | Zbl

[75] Mowshowitz A., “Entropy and the complexity of graphs IV: Entropy measures and graphical structure”, Bull. Math. Biophys., 30 (1968), 533–546 | DOI | MR | Zbl

[76] Narasimhamurthy A., Greene D., Hurley N., Cunningham P., Partitioning large networks without breaking communities, Springer-Verlag, London, 2009 | Zbl

[77] Newman M. E. J., “Detecting community structure in networks”, The European Physical Journal B, 38 (2004), 321–330 | DOI

[78] Newman M. E. J., Girvan M., “Finding and evaluating community structure in networks”, Physical Review E, 69 (2003), 026113, 15 pp. | DOI

[79] Nussinov R., Jacobson A. B., “Fast algorithm for predicting the secondary structure of single-stranded RNA”, PNAS, 77:11 (1980), 6309–6313 | DOI

[80] Ogata H., Fujibuchi W., Goto S., Kanehisa M., “A heuristic graph comparison algorithm and its application to detect functionally”, Nucleic Acids Res., 28:20 (2000), 4021–4028 | DOI

[81] Palla G., Derenyi I., Farkas I., Vicsek T., “Uncovering the overlapping community structure of complex networks in nature and society”, Nature, 435 (2005), 814–818 | DOI

[82] Patil A., Esfahanian A.-H., Xiao L., Liu Y., “Resource allocation using multiple edge-sharing multicast trees”, IEEE Transactions on Vehicular Technology, 58 (2007), 3178–3186

[83] Pothen A., Simon H. D., Liou K. P., “Partitioning sparse matrices with eigenvectors of graphs”, SIAM Journal on Mathematical Analysis, 11 (1990), 430–452 | DOI | MR | Zbl

[84] Pržulj N., “Network comparison using graphlet degree distribution”, Bioinformatics, 23 (2007), e177–e183 | DOI

[85] Randić M., “On characterization of molecular branching”, J. Amer. Chem. Soc., 97 (1975), 6609–6615 | DOI

[86] Randić M., Plavšić D., “Characterization of molecular complexity”, International Journal of Quantum Chemistry, 91 (2002), 20–31 | DOI

[87] Rashevsky N., “Life, information theory, and topology”, Bull. Math. Biophys., 17 (1955), 229–235 | DOI | MR

[88] Rison S. C. G., Thornton J. M., “Pathway evolution, structurally speaking”, Current Opinion in Structural Biology, 12 (2002), 374–382 | DOI

[89] Robinson D. F., Foulds L. R., “Comparison of phylogenetic trees”, Mathematical Biosciences, 53 (1981), 131–147 | DOI | MR | Zbl

[90] Rosselló F., Valiente G., “Graph transformation in molecular biology”, Formal Methods in Software and Systems Modeling, eds. Kreowski H. J., Montanari U., Orejas F., Rozenberg G., Taentzer G., 2005, 116–133 | DOI | MR | Zbl

[91] Schultz H. P., Schultz E. B., Schultz T. P., “Topological organic chemistry. 4. Graph Theory, Matrix Permanents, and Topological Indices of Alkanes”, Journal of Chemical Information and Computer Sciences, 32:1 (1992), 69–72

[92] Selkow S. M., “The tree-to-tree editing problem”, Information Processing Letters, 6 (1977), 184–186 | DOI | MR | Zbl

[93] Semple C., Steel M., Phylogenetics, Graduate Series Mathematics and its Applications, Oxford University Press, 2003 | MR | Zbl

[94] Shannon C. E., Weaver W., The Mathematical Theory of Communication, University of Illinois Press, Urbana, IL, USA, 1997 | MR

[95] Shi J., Malik J., “Normalized cuts and image segmentation”, Proceedings of IEEE conference on computer vision and pattern recognition, CVPR' 97, 1997, 731–737

[96] Simonyi G., “Graph entropy: A survey”, Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20, eds. Cook W., Lovász L., Seymour P., 1995, 399–441 | MR | Zbl

[97] Skorobogatov V. A., Dobrynin A. A., “Metrical analysis of graphs”, Commun. Math. Comp. Chem., 23 (1988), 105–155 | MR

[98] Solé R. V., Valverde S., “Information theory of complex networks: On evolution and architectural constraints”, Lecture Notes in Physics, 650, 2004, 189–207 | DOI | MR | Zbl

[99] Steel M., Penny D., “Parsimony, likelihood, and the role of models in molecular phylogenetics”, Molecular Biology and evolution, 17 (2000), 839–850 | DOI

[100] Steel M., Székely L., Mossel E., “Phylogenetic information complexity: Is testing a tree easier than finding it?”, Journal of Theoretical Biology, 258 (2009), 95–102 | DOI | MR

[101] Tai K. C., “The tree-to-tree correction problem”, Journal of the Association for Computing Machinery, 26 (1979), 422–433 | DOI | MR | Zbl

[102] Todeschini R., Consonni V., Mannhold R., Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, Germany, 2002

[103] Trinajstić N., Chemical Graph Theory, CRC Press, Boca Raton, FL, USA, 1992 | MR

[104] Trucco E., “A note on the information content of graphs”, Bull. Math. Biol., 18:2 (1956), 129–135 | MR

[105] Ulanowicz R. E., “Information theory in ecology”, Computers and Chemistry, 25 (2001), 393–399 | DOI

[106] Vahid F., Dm Le T., “Extending the kernighan/lin heuristic for hardware and software functional partitioning”, Design Automation for Embedded Systems, 2:2 (1997), 237–261 | DOI

[107] Varmuza K., Demuth W., Karlovits M., Scsibrany H., “Binary substructure descriptors for organic compounds”, Croat. Chem. Acta, 78 (2005), 141–149

[108] Wang J., Provan G., “Characterizing the structural complexity of real-world complex networks”, Complex Sciences, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 4, ed. Zhou J., Springer, Berlin–Heidelberg, Germany, 2009, 1178–1189 | DOI

[109] Washietl S., Gesell T., Graph representations and algorithms in computational biology of RNA secondary structure, Structural Analysis of Complex Networks, Birkhäuser; Springer, 2010 (to appear) | MR

[110] Wasserman S., Faust K., Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, Cambridge University Press, 1994 | Zbl

[111] Waterman M. S., “Secondary structure of single-stranded nucleic acids”, Studies on foundations and combinatorics, Advances in mathematics supplementary studies, 1, Academic Press, N.Y., 1978, 167–212 | MR

[112] Wiener H., “Structural determination of paraffin boiling points”, Journal of the American Chemical Society, 69:17 (1947), 17–20 | DOI

[113] Wilkinson D., Huberman B. A., “A method for finding communities of related genes”, PNAS, 101:1 (2004), 5241–5248 | DOI

[114] Xia K., Fu Z., Hou L., “Impacts of protein-protein interaction domains on organism and network complexity”, Genome Res., 18 (2008), 1500–1508 | DOI

[115] Zachary W., “An information flow model for conflict and fission in small groups”, Journal of Anthropological Research, 33 (1977), 452–473

[116] Zuker M., Stiegler P., “Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information”, Nucleic Acids Research, 9:1 (1981), 133–148 | DOI