Analysing structure in complex networks using quality functions evolved by genetic programming
Authors: 
Fergal Reid, Neil HurleyAuthors Info & Claims
Pages 283 - 290
Abstract
When studying complex networks, we are often interested in identifying structures within the networks. Previous work has successfully used algorithmically identified network structures to predict functional groups; for example, where structures extracted from protein-protein interaction networks have been predictive of functional protein complexes. One way structures in complex networks have previously been described is as collections of nodes that maximise a local quality function.
For a particular set of structures, we search the space of quality functions using Genetic Programming, to find a function that locally describes that set of structures. This technique allows us to investigate the common network properties of defined sets of structures. We also use this technique to classify and differentiate between different types of structure. We apply this method on several synthetic benchmarks, and on a protein-protein interaction network. Our results indicate this is a useful technique of investigating properties that sets of network structures have in common.
References
[1]
B. Adamcsek, G. Palla, I. Farkas, I. Derényi, and T. Vicsek. CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics, 22(8):1021, 2006.
[2]
M. Altaf-Ul-Amin, Y. Shinbo, K. Mihara, K. Kurokawa, and S. Kanaya. Development and implementation of an algorithm for detection of protein complexes in large interaction networks. BMC bioinformatics, 7(1):207, 2006.
[3]
D. Bamber. The area above the ordinal dominance graph and the area below the receiver operating characteristic graph. Journal of mathematical psychology, 12(4):387--415, 1975.
[4]
A. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509, 1999.
[5]
A. Clauset. Finding local community structure in networks. Physical Review E, 72(2):26132, 2005.
[6]
S. Collins, P. Kemmeren, X. Zhao, J. Greenblatt, F. Spencer, F. Holstege, J. Weissman, and N. Krogan. Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae. Molecular & Cellular Proteomics, 6(3):439, 2007.
[7]
S. Fortunato. Community detection in graphs. Physics Reports, 2009.
[8]
A. Gog, D. Dumitrescu, and B. Hirsbrunner. Community detection in complex networks using collaborative evolutionary algorithms. Advances in Artificial Life, pages 886--894, 2007.
[9]
M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. Witten. The WEKA data mining software: An update. ACM SIGKDD Explorations Newsletter, 11(1):10--18, 2009.
[10]
J. Koza. Genetic programming: on the programming of computers by means of natural selection. The MIT press, 1992.
[11]
A. Lancichinetti, S. Fortunato, and J. Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11:033015, 2009.
[12]
C. Lee, F. Reid, A. McDaid, and N. Hurley. Detecting highly overlapping community structure by greedy clique expansion. KDD SNA 2010, 2010.
[13]
X. Liu, D. Li, S. Wang, and Z. Tao. Effective algorithm for detecting community structure in complex networks based on GA and Clustering. Computational Science--ICCS 2007, pages 657--664, 2007.
[14]
R. Luce and A. Perry. A method of matrix analysis of group structure. Psychometrika, 14(2):95--116, 1949.
[15]
F. Luo, J. Wang, and E. Promislow. Exploring local community structures in large networks. Web Intelligence and Agent Systems, 6(4):387--400, 2008.
[16]
J. Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods, pages 185--208. MIT press, 1999.
[17]
J. Quinlan. C4. 5: programs for machine learning. Morgan Kaufmann, 1993.
[18]
R. Sharan, T. Ideker, B. Kelley, R. Shamir, and R. Karp. Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. Journal of Computational Biology, 12(6):835--846, 2005.
[19]
H. Simon. The architecture of complexity. Proceedings of the American Philosophical Society, pages 467--482, 1962.
[20]
J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32(4):425--443, 1969.
[21]
D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, 1998.
[22]
G. Wilson and W. Banzhaf. Discovery of email communication networks from the Enron corpus with a genetic algorithm using social network analysis. In Evolutionary Computation, 2009. CEC'09. IEEE Congress on, pages 3256--3263. IEEE, 2009.
Index Terms
- Analysing structure in complex networks using quality functions evolved by genetic programming
Recommendations
A Genetic Algorithm Based on Modularity Density for Detecting Community Structure in Complex Networks
CIS '10: Proceedings of the 2010 International Conference on Computational Intelligence and SecurityThe problem of community structure detection in complex networks has been intensively investigated in recent years. Many algorithms were proposed based on optimization modularity. To overcome the solution limitation drawbacks of modularity function, as ...
Structure identification of uncertain general complex dynamical networks with time delay
It is well known that many real-world complex networks have various uncertain information, such as unknown or uncertain topological structure and node dynamics. The structure identification problem has theoretical and practical importance for uncertain ...
Adjusting assortativity in complex networks
ACMSE '14: Proceedings of the 2014 ACM Southeast ConferenceAssortativity has been widely studied for understanding the structure and function of complex networks. Assortative is defined as an association of items with other items having similar characteristics. The research has shown that assortativity has a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2011
2140 pages
Copyright © 2011 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2011
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '11
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 164Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in