Practical k-agents search algorithm towards information retrieval in complex networks | World Wide Web Skip to main content
Springer Nature Link
Log in

Practical k-agents search algorithm towards information retrieval in complex networks

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

Spanking information retrieval in large-scale Web and network has attracted increasing interest in the research community, many typical approaches have been recalled such as greedy, random-walk and high degree seeking since the search capabilities of complex networks are proved by Kleinberg in 2000. Unfortunately, the retrieval efficiency of these classic approaches is not ideal, and they are only suitable for the specific networks due to their defects. The motivation of this paper is to increase the retrieval efficiency, and we thus proposed a novel k-agents search approach for different types of networks which searches the networks with k-agents, simultaneously. Besides, to better test the efficiency of algorithms, a new evaluation method which considers search steps and query information both is put forward to measure the cost of the search algorithm. The complexity analysis also will be discussed, and the comparison with other algorithms will be displayed in detail to show its superiority. In the end, for the purpose of displaying a universe application of our algorithm, the simulations in WS (proposed by Watts and Strogatz), NW (proposed by Newman and Watts) small-world and BA (proposed by Barabái and Albert) scale-free network model are carried out to illustrate the performance of the proposed method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8

Similar content being viewed by others

References

  1. Adamic, L.A., Lukose, R.M., Puniyani, A.R., Huberman, B.A.: Search in power-law networks. Phys. Rev. E 64, 046135 (2001)

    Article  Google Scholar 

  2. Adamic, L.A., Lukose, R.M., Huberman, B.A.: Local search in unstructured networks. In: Bornholdt, S., Schuster, H.G. (eds.) Handbook of Graphs and Networks, pp 295–317. Wiley-VCH (2003)

  3. Al-asadi, T.A., Obaid, A.J., Hidayat, R., et al.: A survey on web mining techniques and applications. International Journal on Advanced Science Engineering and Information Technology 7, 1178–1184 (2017)

    Article  Google Scholar 

  4. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bennett, L., Liu, S., Papageorgiou, L.G., Tsoka, S.: Detection of disjoint and overlapping modules in weighted complex networks. Adv. Complex Syst. 15, 1150023 (2012)

    Article  MathSciNet  Google Scholar 

  6. Berger, A., Lafferty, J.: Information retrieval as statistical translation. ACM SIGIR Forum 51, 219–226 (2017)

    Article  Google Scholar 

  7. Cai, B., Wang, H.Y., Zheng, H., Wang, H.: An improved random walk based clustering algorithm for community detection in complex networks. In: 2011 IEEE International Conference on Systems, Man, and Cybernetics, pp 2162–2167 (2011)

  8. Cajueiro, D.: Optimal navigation for characterizing the role of the nodes in complex networks. Physica A 389, 1945–1954 (2010)

    Article  Google Scholar 

  9. Cao, Y., Yu, W., Ren, W., et al.: An overview of recent progress in the study of distributed multi-agent coordination. IEEE Trans. Ind. Inf. 9, 427–438 (2013)

    Article  Google Scholar 

  10. Chau, M., Zeng, D., Chen, H., et al.: Design and evaluation of a multi-agent collaborative Web mining system. Decis. Support. Syst. 35, 167–183 (2003)

    Article  Google Scholar 

  11. Chen, D., Fan, Y., Shang, M.: A fast and efficient heuristic algorithm for detecting community structures in complex networks. Physica A 388, 2741–2749 (2009)

    Article  Google Scholar 

  12. Chen, L., Chen, J., Guan, Z., Zhang, X., Zhang, D.: Optimization of transport protocols in complex networks. Physica A 391, 3336–3341 (2012)

    Article  Google Scholar 

  13. Cohen, R., Havlin, S.: Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 01 1–4 (2003)

    Article  Google Scholar 

  14. Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Phys. Rev. Lett. 85, 4633–4636 (2002)

    Article  Google Scholar 

  15. Drias, Y., Pasi, G.: A collaborative approach to Web information foraging based on multi-agent systems. In: Proceedings of the International Conference on Web Intelligence, pp 365–371 (2017)

  16. Feng, M., Qu, H., Yi, Z.: Highest degree likelihood search algorithm using a state transition matrix for complex networks. IEEE Trans. Circuits Syst. Regul. Pap. 61, 2941–2950 (2014)

    Article  Google Scholar 

  17. Feng, M., Qu, H., Yi, Z., et al.: Evolving scale-free networks by poisson process: modeling and degree distribution. IEEE Transactions on Cybernetics 46, 1144–1155 (2016)

    Article  Google Scholar 

  18. Gao, L., Guo, Z., Zhang, H., Xu, X., Shen, H.: Video captioning with attention-based LSTM and semantic consistency. IEEE Trans. Multimedia 19, 2045–2055 (2017)

    Article  Google Scholar 

  19. Gao, L., Song, J., Liu, X., Shao, J., Liu, J., Shao, J.: Learning in high-dimensional multimedia data: the state of the art. Multimedia Systems 23, 303–313 (2017)

    Article  Google Scholar 

  20. Hughes, B.D.: Random Walks and Random Environments. Clarendon Press, Oxford (1996)

    MATH  Google Scholar 

  21. Jasch, F., Blumen, A.: Target problem on small-world networks. Phys. Rev. E 63, 041108 (2001)

    Article  Google Scholar 

  22. Kim, B.J., Yoon, C.N., Han, S.K., Jeong, H.: Path finding strategies in scale-free networks. Phys. Rev. E 65, 027103 (2002)

    Article  Google Scholar 

  23. Kleinberg, J.M.: Navigation in a small world. Nature 406, 406–845 (2000)

    Article  Google Scholar 

  24. Krapivsky, P.L., Redner, S., Leyvraz, F.: Connectivity of growing random networks. Phys. Rev. Lett. 85, 4629–4632 (2000)

    Article  Google Scholar 

  25. Liu, M., Xu, Y., Mohammed, A.W.: Decentralized opportunistic spectrum resources access model and algorithm toward cooperative ad-hoc networks. PloS one 11, e0145526 (2016)

    Article  Google Scholar 

  26. Liu, X., Li, Z., Deng, C., Tao, D.: Distributed adaptive binary quantization for fast nearest neighbor search. IEEE Trans. Image Process. 26, 5324–5336 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lu, L., Zhou, T.: Link prediction in complex networks: a survey. Physica A 390, 1150–1170 (2011)

    Article  Google Scholar 

  28. Newman, M.E.J., Watts, D.J.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341–346 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  29. Rosvall, M., Trusina, A., Minnhagen, P., Sneppen, K.: Hide-and-seek on complex networks. Europhys. Lett. 69, 853–859 (2005)

    Article  Google Scholar 

  30. Saini, S., Pandey, H.M.: Review on Web content mining techniques. Int. J. Comput. Appl. 18, 118 (2015)

    Google Scholar 

  31. Sharma, D.K., Sharma, A.K.: Deep Web information retrieval process: a technical survey. IJITWE 5(1), 1–22 (2010)

    MathSciNet  Google Scholar 

  32. Shi, C., Yan, Z.Y.: A genetic algorithm for detecting communities in large-scale complex networks. Adv. Complex Syst. 13, 3–17 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  33. Song, J., Gao, L., Liu, L., Zhu, X., Sebe, N.: Quantization-based hashing: a general framework for scalable image and video retrieval. Pattern Recogn. 75, 175–187 (2018)

    Article  Google Scholar 

  34. Thadakamalla, H.P., Albert, R., Kumara, S.R.T.: Search in spatial scale-free networks. New J. Phys. 9, 190 (2007)

    Article  Google Scholar 

  35. Wang, X., Gao, L., Wang, P., Sun, X., Liu, X.: Two-stream 3D convNet fusion for action recognition in videos with arbitrary size and length. In: IEEE Transactions on Multimedia. In press (2018)

  36. Watts, D.J., Strogatz, S.H.: Collective dynamic of ‘small-world’ networks. Nature 393, 440–442 (1998)

    Article  MATH  Google Scholar 

  37. Watts, D.J., Dodds, P.S., Newman, M.E.J.: Identity and search in social networks. Science 296(5571), 1302–1305 (2002)

    Article  Google Scholar 

  38. Witten, I.H., Frank, E., Hall, M.A., et al.: Data mining: practical machine learning tools and techniques, p 223. Morgan Kaufmann, Burlington (2016)

    Google Scholar 

  39. XinLing, S., LiJun, Z.: Search in complex networks with local efficient information. In: International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), pp 359–362 (2011)

  40. Zhu, X., Zhang, S., Hu, R., Zhu, Y., Song, J.: Local and global structure preservation for robust unsupervised spectral feature selection. In: IEEE Transactions on Knowledge and Data Engineering. In press (2018)

Download references

Acknowledgments

This work is partially supported by the National Natural Science Foundation of China (Grant No.61602093).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 611731, People’s Republic of China

    Pengfei Liu, Minyu Feng & Ming Liu

Authors
  1. Pengfei Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Minyu Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ming Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pengfei Liu.

Additional information

This article belongs to the Topical Collection: Special Issue on Deep vs. Shallow: Learning for Emerging Web-scale Data Computing and Applications

Guest Editors: Jingkuan Song, Shuqiang Jiang, Elisa Ricci, and Zi Huang

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, P., Feng, M. & Liu, M. Practical k-agents search algorithm towards information retrieval in complex networks. World Wide Web 22, 885–905 (2019). https://doi.org/10.1007/s11280-018-0527-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11280-018-0527-8

Keywords

Search

Navigation