Journal Mobile Options
Table of Contents
Vol. 3, No. 1-3, 2006
Issue release date: August 2006
Section title: Network modelling
ComPlexUs 2006;3:158–168
(DOI:10.1159/000094197)

Is Selection Optimal for Scale-Free Small Worlds?

Palotai Z.a · Farkas C.b · Lorincz A.a
aDepartment of Information Systems, Eötvös Loránd University, Budapest, Hungary; bDepartment of Computer Science and Engineering, University of South Carolina, Columbia, S.C., USA
email Corresponding Author

Abstract

The ‘no free lunch theorem’ claims that for the set of all problems no algorithm performs better than random search and, thus, selection can be advantageous only on a limited set of problems. In this paper we investigate how the topological structure of the environment influences algorithmic efficiency. We study the performance of algorithms, using selective learning, reinforcement learning, and their combinations, in random, scale-free, and scale-free small world (SFSW) environments. The learning problem is to search for novel, not-yet-found information. We ran our experiments on a large news site and on its downloaded portion. Controlled experiments were performed on this downloaded portion: we modified the topology, but preserved the publication time of the news. Our empirical results show that the selective learning is the most efficient in SFSW topology. In non-small world topologies, however, the combination of the selective and reinforcement learning algorithms performs the best.

© 2006 S. Karger AG, Basel


  

Key Words

  • Scale-free small world
  • No free lunch theorem
  • Internet

References

  1. Wolpert DH, Macready WG: No free lunch theorems for optimization. IEEE Trans Evolutionary Comput 1997; 1: 67–82.
  2. Barabási A, Albert R, Jeong H: Scale-free characteristics of random networks: the topology of the world wide web. Physica A 2000; 281: 69–77.

    External Resources

  3. Albert R, Barabási A: Statistical mechanics of complex networks. Rev Mod Phys 2002; 74: 47–91.

    External Resources

  4. Annunziato M, Huerta R, Lucchetti M, Tsimring LS: Artificial life optimization over complex networks. 4th International ICSC Symposium on Engineering of Intelligent Systems, Funchal, 2004.
  5. Kleinberg J, Lawrence S: The structure of the web. Science 2001; 294: 1849–1850.
  6. Sutton R, Barto A: Reinforcement Learning: an Introduction. Cambridge, MIT Press, 1998.
  7. Eiben AE, Smith JE: Introduction to Evolutionary Computing. Berlin, Springer, 2003.
  8. Fryxell J, Lundberg P: Individual Behavior and Community Dynamics. London, Chapman & Hall, 1998.
  9. Clark C, Mangel M: Dynamic State Variable Models in Ecology: Methods and Applications. Oxford, Oxford University Press, 2000.
  10. Kampis G: Self-Modifying Systems in Biology and Cognitive Science: a New Framework for Dynamics, Information and Complexity. Oxford, Pergamon, 1991.
  11. Csányi V: Evolutionary Systems and Society: a General Theory of Life, Mind, and Culture. Durham, Duke University Press, 1989.
  12. Pachepsky E, Taylor T, Jones S: Mutualism promotes diversity and stability in a simple artificial ecosystem. Artif Life 2002; 8/1: 5–24.

    External Resources

  13. Tesauro GJ: Temporal difference learning and td-gammon. Commun ACM 1995; 38: 58–68.

    External Resources

  14. Mataric MJ: Reinforcement learning in the multi-robot domain. Autonomous Robots 1997; 4/1: 73–83.

    External Resources

  15. Stafylopatis A, Blekas K: Autonomous vehicle navigation using evolutionary reinforcement learning. Eur J Operational Res 1998; 108: 306–318.

    External Resources

  16. Moriarty D, Schultz A, Grefenstette J: Evolutionary algorithms for reinforcement learning. J Artif Intell Res 1999; 11: 199–229.
  17. Tuyls K, Heytens D, Nowe A, Manderick B: Extended replicator dynamics as a key to reinforcement learning in multi-agent systems; in Lavrac N, et al (eds): ECML 2003, LNAI 2837. Berlin, Springer, 2003, pp 421–431.
  18. Kondo T, Ito K: A reinforcement learning with evolutionary state recruitment strategy for autonomous mobile robots control. Robot Auton Syst 2004; 46: 11–124.

    External Resources

  19. Kökai I, Lörincz A: Fast adapting value estimation based hybrid architecture for searching the world-wide web. Appl Soft Comput 2002; 2: 11–23.

    External Resources

  20. Lörincz A, Kókai I, Meretei A: Intelligent high-performance crawlers used to reveal topic-specific structure of the WWW. Int J Founds Comp Sci 2002; 13: 477–495.

    External Resources

  21. Palotai Z, Gábor B, Lörincz A: Adaptive highlighting of links to assist surfing on the internet. Int J Inf Technol Decis Making 2005; 4: 117–139.

    External Resources

  22. Angkawattanawit N, Rungsawang A: Learnable topic-specific web crawler; in Abraham A, Ruiz-del-Solar J, Köppen M (eds): Hybrid Intelligent Systems. Amsterdam, IOS Press, 2002, pp 573–582.
  23. Menczer F: Complementing search engines with online web mining agents. Decis Support Syst 2003; 35: 195–212.
  24. Risvik KM, Michelsen R: Search engines and web dynamics. Comput Networks 2002; 32: 289–302.

    External Resources

  25. Cho J, Garcia-Molina H: Effective page refresh policies for web crawlers. ACM Trans Database Syst 2003; 28: 390–426.

    External Resources

  26. Edwards J, McCurley K, Tomlin J: An adaptive model for optimizing performance of an incremental web crawler. Proceedings of the 10th International Conference on World Wide Web, Hong Kong, 2001, pp 106–113.
  27. Szita I, Lörincz A: Kalman filter control embedded into the reinforcement learning framework. Neural Comput 2004; 16: 491–499.
  28. Schultz W: Multiple reward systems in the brain. Nat Rev Neurosci 2000; 1: 199–207.
  29. Joachims T: A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization; in Fisher DH (ed): Proceedings of ICML-97, 14th International Conference on Machine Learning (Nashville, US, 1997). San Francisco, Morgan Kaufmann, 1997, pp 143–151.
  30. Boley D: Principal direction division partitioning. Data Mining Knowledge Discovery 1998; 2: 325–344.

    External Resources

  31. Sutton R: Learning to predict by the method of temporal differences. Mach Learn 1988; 3: 9–44.
  32. Watts DJ, Strogatz SH: Collective dynamics of ‘small-world’ networks. Nature 1998; 393: 440–442.

  

Author Contacts

A. Lörincz
Department of Information Systems, Eötvös Loránd University
Pázmány Péter sétány 1/c, HU–1117 Budapest (Hungary)
Tel. +36 1 209 0555/8473, Fax +36 1 381 2140, E-Mail andras.lorincz@elte.hu

  

Article Information

Published online: August 25, 2006
Number of Print Pages : 11
Number of Figures : 3, Number of Tables : 2, Number of References : 32

  

Publication Details

Complexus (Modelling in Systems Biology, Social, Cognitive and Information Sciences)

Vol. 3, No. 1-3, Year 2006 (Cover Date: August 2006)

Journal Editor: Atlan, H. (Paris/Jerusalem)
ISSN: 1424–8492 (print), 1424–8506 (Online)

For additional information: http://www.karger.com/CPU


Copyright / Drug Dosage / Disclaimer

Copyright: All rights reserved. No part of this publication may be translated into other languages, reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording, microcopying, or by any information storage and retrieval system, without permission in writing from the publisher or, in the case of photocopying, direct payment of a specified fee to the Copyright Clearance Center.
Drug Dosage: The authors and the publisher have exerted every effort to ensure that drug selection and dosage set forth in this text are in accord with current recommendations and practice at the time of publication. However, in view of ongoing research, changes in goverment regulations, and the constant flow of information relating to drug therapy and drug reactions, the reader is urged to check the package insert for each drug for any changes in indications and dosage and for added warnings and precautions. This is particularly important when the recommended agent is a new and/or infrequently employed drug.
Disclaimer: The statements, opinions and data contained in this publication are solely those of the individual authors and contributors and not of the publishers and the editor(s). The appearance of advertisements or/and product references in the publication is not a warranty, endorsement, or approval of the products or services advertised or of their effectiveness, quality or safety. The publisher and the editor(s) disclaim responsibility for any injury to persons or property resulting from any ideas, methods, instructions or products referred to in the content or advertisements.

Abstract

The ‘no free lunch theorem’ claims that for the set of all problems no algorithm performs better than random search and, thus, selection can be advantageous only on a limited set of problems. In this paper we investigate how the topological structure of the environment influences algorithmic efficiency. We study the performance of algorithms, using selective learning, reinforcement learning, and their combinations, in random, scale-free, and scale-free small world (SFSW) environments. The learning problem is to search for novel, not-yet-found information. We ran our experiments on a large news site and on its downloaded portion. Controlled experiments were performed on this downloaded portion: we modified the topology, but preserved the publication time of the news. Our empirical results show that the selective learning is the most efficient in SFSW topology. In non-small world topologies, however, the combination of the selective and reinforcement learning algorithms performs the best.

© 2006 S. Karger AG, Basel


  

Author Contacts

A. Lörincz
Department of Information Systems, Eötvös Loránd University
Pázmány Péter sétány 1/c, HU–1117 Budapest (Hungary)
Tel. +36 1 209 0555/8473, Fax +36 1 381 2140, E-Mail andras.lorincz@elte.hu

  

Article Information

Published online: August 25, 2006
Number of Print Pages : 11
Number of Figures : 3, Number of Tables : 2, Number of References : 32

  

Publication Details

Complexus (Modelling in Systems Biology, Social, Cognitive and Information Sciences)

Vol. 3, No. 1-3, Year 2006 (Cover Date: August 2006)

Journal Editor: Atlan, H. (Paris/Jerusalem)
ISSN: 1424–8492 (print), 1424–8506 (Online)

For additional information: http://www.karger.com/CPU


Article / Publication Details

First-Page Preview
Abstract of Network modelling

Published online: 9/1/2006
Issue release date: August 2006

Number of Print Pages: 11
Number of Figures: 3
Number of Tables: 2

ISSN: 1424-8492 (Print)
eISSN: 1424-8506 (Online)

For additional information: http://www.karger.com/CPU


Copyright / Drug Dosage

Copyright: All rights reserved. No part of this publication may be translated into other languages, reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording, microcopying, or by any information storage and retrieval system, without permission in writing from the publisher or, in the case of photocopying, direct payment of a specified fee to the Copyright Clearance Center.
Drug Dosage: The authors and the publisher have exerted every effort to ensure that drug selection and dosage set forth in this text are in accord with current recommendations and practice at the time of publication. However, in view of ongoing research, changes in goverment regulations, and the constant flow of information relating to drug therapy and drug reactions, the reader is urged to check the package insert for each drug for any changes in indications and dosage and for added warnings and precautions. This is particularly important when the recommended agent is a new and/or infrequently employed drug.
Disclaimer: The statements, opinions and data contained in this publication are solely those of the individual authors and contributors and not of the publishers and the editor(s). The appearance of advertisements or/and product references in the publication is not a warranty, endorsement, or approval of the products or services advertised or of their effectiveness, quality or safety. The publisher and the editor(s) disclaim responsibility for any injury to persons or property resulting from any ideas, methods, instructions or products referred to in the content or advertisements.

References

  1. Wolpert DH, Macready WG: No free lunch theorems for optimization. IEEE Trans Evolutionary Comput 1997; 1: 67–82.
  2. Barabási A, Albert R, Jeong H: Scale-free characteristics of random networks: the topology of the world wide web. Physica A 2000; 281: 69–77.

    External Resources

  3. Albert R, Barabási A: Statistical mechanics of complex networks. Rev Mod Phys 2002; 74: 47–91.

    External Resources

  4. Annunziato M, Huerta R, Lucchetti M, Tsimring LS: Artificial life optimization over complex networks. 4th International ICSC Symposium on Engineering of Intelligent Systems, Funchal, 2004.
  5. Kleinberg J, Lawrence S: The structure of the web. Science 2001; 294: 1849–1850.
  6. Sutton R, Barto A: Reinforcement Learning: an Introduction. Cambridge, MIT Press, 1998.
  7. Eiben AE, Smith JE: Introduction to Evolutionary Computing. Berlin, Springer, 2003.
  8. Fryxell J, Lundberg P: Individual Behavior and Community Dynamics. London, Chapman & Hall, 1998.
  9. Clark C, Mangel M: Dynamic State Variable Models in Ecology: Methods and Applications. Oxford, Oxford University Press, 2000.
  10. Kampis G: Self-Modifying Systems in Biology and Cognitive Science: a New Framework for Dynamics, Information and Complexity. Oxford, Pergamon, 1991.
  11. Csányi V: Evolutionary Systems and Society: a General Theory of Life, Mind, and Culture. Durham, Duke University Press, 1989.
  12. Pachepsky E, Taylor T, Jones S: Mutualism promotes diversity and stability in a simple artificial ecosystem. Artif Life 2002; 8/1: 5–24.

    External Resources

  13. Tesauro GJ: Temporal difference learning and td-gammon. Commun ACM 1995; 38: 58–68.

    External Resources

  14. Mataric MJ: Reinforcement learning in the multi-robot domain. Autonomous Robots 1997; 4/1: 73–83.

    External Resources

  15. Stafylopatis A, Blekas K: Autonomous vehicle navigation using evolutionary reinforcement learning. Eur J Operational Res 1998; 108: 306–318.

    External Resources

  16. Moriarty D, Schultz A, Grefenstette J: Evolutionary algorithms for reinforcement learning. J Artif Intell Res 1999; 11: 199–229.
  17. Tuyls K, Heytens D, Nowe A, Manderick B: Extended replicator dynamics as a key to reinforcement learning in multi-agent systems; in Lavrac N, et al (eds): ECML 2003, LNAI 2837. Berlin, Springer, 2003, pp 421–431.
  18. Kondo T, Ito K: A reinforcement learning with evolutionary state recruitment strategy for autonomous mobile robots control. Robot Auton Syst 2004; 46: 11–124.

    External Resources

  19. Kökai I, Lörincz A: Fast adapting value estimation based hybrid architecture for searching the world-wide web. Appl Soft Comput 2002; 2: 11–23.

    External Resources

  20. Lörincz A, Kókai I, Meretei A: Intelligent high-performance crawlers used to reveal topic-specific structure of the WWW. Int J Founds Comp Sci 2002; 13: 477–495.

    External Resources

  21. Palotai Z, Gábor B, Lörincz A: Adaptive highlighting of links to assist surfing on the internet. Int J Inf Technol Decis Making 2005; 4: 117–139.

    External Resources

  22. Angkawattanawit N, Rungsawang A: Learnable topic-specific web crawler; in Abraham A, Ruiz-del-Solar J, Köppen M (eds): Hybrid Intelligent Systems. Amsterdam, IOS Press, 2002, pp 573–582.
  23. Menczer F: Complementing search engines with online web mining agents. Decis Support Syst 2003; 35: 195–212.
  24. Risvik KM, Michelsen R: Search engines and web dynamics. Comput Networks 2002; 32: 289–302.

    External Resources

  25. Cho J, Garcia-Molina H: Effective page refresh policies for web crawlers. ACM Trans Database Syst 2003; 28: 390–426.

    External Resources

  26. Edwards J, McCurley K, Tomlin J: An adaptive model for optimizing performance of an incremental web crawler. Proceedings of the 10th International Conference on World Wide Web, Hong Kong, 2001, pp 106–113.
  27. Szita I, Lörincz A: Kalman filter control embedded into the reinforcement learning framework. Neural Comput 2004; 16: 491–499.
  28. Schultz W: Multiple reward systems in the brain. Nat Rev Neurosci 2000; 1: 199–207.
  29. Joachims T: A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization; in Fisher DH (ed): Proceedings of ICML-97, 14th International Conference on Machine Learning (Nashville, US, 1997). San Francisco, Morgan Kaufmann, 1997, pp 143–151.
  30. Boley D: Principal direction division partitioning. Data Mining Knowledge Discovery 1998; 2: 325–344.

    External Resources

  31. Sutton R: Learning to predict by the method of temporal differences. Mach Learn 1988; 3: 9–44.
  32. Watts DJ, Strogatz SH: Collective dynamics of ‘small-world’ networks. Nature 1998; 393: 440–442.