Class Characterization via Optimization in Complex Networks

• Lilian Berton USP
• Liang Zhao USP

Abstract

Complex networks have emerged as an important way of data representation and abstraction able of capturing the topological structure presented in databases. This work proposes a method for building a network from a vector based dataset. It is based on the optimization of an energy function that considers purity and extension measures of the network. The constructed network was used to characterize mixing level among data classes in classification problem. Class characterization is an important issue, but it is not well studied. Therefore, we consider this work a contribution in this direction.

References

Albert, R., Jeong, H. e Barabási, A. L. (1999) “Internet: Diameter of the world wide web”. Nature 401, p.130-131.

Baldi, P. e Brunak, S. (1998) Bioinformatics: the machine learning approach, MIT Press.

Barabási, A. L. e Albert, R. (1999) “Emergence of scaling in random networks”, Science 286, p. 509-512.

Belkin, M. Niyogi, P. (2003) “Laplacian eigenmaps for dimensionality reduction and data representation”, Neural Computation 15, p. 1373-1396.

Boccaletti, S., Ivanchenko, M., Latora, V., Pluchino, A. e Rapisarda, A. (2007) “Detecting complex network modularity by dynamical clustering”, Physical Review E 75, p. 1-4.

Bornholdt, S. e Schuster, H. G. (2003) Handbook of Graphs and Networks: From the Genome to the Internet, Wiley-VCH.

Cancho, F. e Solé, R. V. (2003) “Optimization in complex networks. Statistical Mechanics of Complex Networks”, Lecture Notes in Physics 625, p. 114-125.

Cook, D. J. e Holder, L. B. (2000) “Graph-based data mining”, IEEE Intelligent Systems 15, p. 32-41.

Erdös, P. e Rényi, A. (1959) “On random graphs”, Publicationes Mathematicae 6, p. 290-297.

Faloutsos, M., Faloutsos, P. e Faloutsos, C. (1999) “On power-law relationship of the internet topology”, Computer Communication Review 29, p. 251-262.

LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W. e Jackel, L. D. (1989) “Backpropagation applied to handwritten zip code recognition”, Neural Computation 1, p. 541-551.

Lopes, A. A., Bertini, Jr. J. R., Motta, R. e Zhao, L. (2009) “Classification Based on the Optimal K-Associated Network”, Proceedings of The First International Conference on Complex Sciences: Theory and Applications, p. 1-11.

Mitchell, T. M. (1997) Machine learning. McGraw-Hill Series in Computer Science, McGrawHill.

Newman, M. E. J. (2004) “Fast algorithm for detecting community structure in networks”, Physical Review E 69 066133.

Newman, M. E. J. e Girvan, M. (2004) “Finding and evaluating community structure in networks”, Physical Review E 69 026113.

Quiles, M. G., Zhao, L., Alonso, R. L. e Romero, R. A. F. (2008) “Particle competition for complex network community detection”, Chaos 18, p. 1-10.

Reichardt, J. e Bornholdt, S. (2004) “Detecting fuzzy community structures in complex networks with a Potts model” Physical Review Letters 93, p. 1-4.

Scott, J. (2000) Social network analysis: a handbook, Sage.

Sponrs, O. (2002) “Networks analysis, complexity, and brain function”, Complexity 8, p. 56-60.

Von Luxburg, U. (2007) “A tutorial on spectral clustering”, Statistical Computation 17, p. 395416.

Watts, D. J. e Strogatz, S. H. (1998) “Collective dynamics of „small-world‟ networks”, Nature 393, p. 440-442.

Wolpert, D. H. e Macready, W. G. (1997) No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation 1, p. 67.

Zhou, H. (2003a) “Network landscape from a Brownian particlés perspective”. Physical Review E 67 041908.

Zhou, H. (2003b) “Distance, dissimilarity index, and network community structure”. Physical Review E 67 061901.

Zhu, X. (2005) “Semi-supervised learning literature review”. Technical Reporter 1530, Computer-Science, University of Wisconsin-Madison.