[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Graph Theoretic Topological Analysis of Web Service Networks

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

Using graph theory, we analyze the topological landscape of web service networks formed by real-world data set, either downloaded from web service repositories or crawled by a search engine. We first propose a flexible framework to study syntactic web service matchmaking in a unified manner. Under the framework, then, the data set is analyzed from diverse perspectives and granularity. By and large, the data set is shown to exhibit small world network well and power-law-like distribution to some extent. Finally, using random graph theory, we demonstrate how to accurately estimate the size of the giant component of such web service networks.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akkiraju, R., Farrell, J., Miller, J., Nagarajan, M., Schmidt, M.-T., Sheth, A., Verma, K.: Web service semantics—WSDL-S. W3C Member submission (2005)

  2. Akkiraju, R., Srivastava, B., Ivan, A.-A., Goodwin, R., Syeda-Mahmood, T.: SEMAPLAN: combining planning with semantic matching to achieve web service composition. In: Internatioal Conference on Web Services (ICWS), pp. 37–44 (2006)

  3. Albert, R., Barabasi, A.-L.: Topology of evolving networks: local events and universality. Phys. Rev. Lett. 85, 5234–5237 (2000)

    Article  Google Scholar 

  4. Albert, R., Jeong, H., Barabasi, A.-L.: The diameter of the world wide web. Nature 401, 130–131 (1999)

    Article  Google Scholar 

  5. Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval. Addison-Wesley, Reading (1999)

    Google Scholar 

  6. Bellur, U., Kulkarni, R.: Improved matchmaking algorithm for semantic web services based on bipartite graph matching. In: Internatioal Conference on Web Services (ICWS), pp. 86–93 (2007)

  7. Bianchini, D., Antonellis, V.D., Melchiori, M.: Flexible semantic-based service matchmaking and discovery. World Wide Web 11(2), 227–251 (2008)

    Article  Google Scholar 

  8. Bilenko, M., Cohen, W., Fienberg, S., Mooney, J., Ravikumar, R.: Adaptive name matching in information integration. IEEE Intell. Syst. 18(5), 16–23 (2003)

    Article  Google Scholar 

  9. Blake, M.B., Nowlan, M.F.: A web service recommender system using enhanced syntactical matching. In: Internatioal Conference on Web Services (ICWS), pp. 575–582 (2007)

  10. Cai, H.: Scale-free web services. In: Internatioal Conference on Web Services (ICWS), pp. 288–295 (2007)

  11. Cibrán, M.A., Verheecke, B., Vanderperren, W., Suvée, D., Jonckers, V.: Aspect-oriented programming for dynamic web service selection, integration and management. World Wide Web 10(3), 211–242 (2007)

    Article  Google Scholar 

  12. De Bruijn, J., Fensel, D., Keller, U., Kifer, M., Lausen, H., Krummenacher, R., Polleres, A., Predoiu, L.: Web service modeling language (WSML). W3C Member submission (2005)

  13. Denning, P.J.: Network laws. Commun. ACM 47(11), 15–20 (2004)

    Article  Google Scholar 

  14. Dong, X., Halevy, A., Madhavan, J., Nemes, E., Zhang, J.: Similarity search for web services. In: International Conference on Very Large Data Bases (VLDB), pp. 372–383 (2004)

  15. Fan, J., Kambhampati, S.: A snapshot of public web services. SIGMOD Rec. 34(1), 24–32 (2005)

    Article  Google Scholar 

  16. Fellbaum, C. (ed.): WordNet: An Electronic Lexical Database. MIT, Cambridge (1998)

    MATH  Google Scholar 

  17. Kil, H., Oh, S.-C., Lee, D.: On the topological landscape of web services matchmaking. In: VLDB Workshop on Semantic Matchmaking and Resource Retrieval. CEUR, vol. 178, pp. 19–34 (2006)

  18. Lécué, F., Delteil, A., Léger, A.: Applying abduction in semantic web service composition. In: Internatioal Conference on Web Services (ICWS), pp. 94–101 (2007)

  19. Li, L., Horrocks, I.: A software framework for matchmaking based on semantic web technology. In: International World Wide Web Conference (WWW), pp. 331–339 (2003)

  20. Maedche, A., Staab, S.: Measuring similarity between ontologies. In: European Conference on Knowledge Acquisition and Management (EKAW), pp. 251–263 (2002)

  21. Maguitman, A.G., Menczer, F., Erdinc, F., Roinestad, H., Vespignani, A.: Algorithmic computation and approximation of semantic similarity. World Wide Web 9(4), 431–456 (2006)

    Article  Google Scholar 

  22. Martin, D., Burstein, M., Hobbs, E., Lassila, O., Mcdermott, D., Mcilraith, S., Narayanan, S., Parsia, B., Payne, T., Sirin, E., Srinivasan, N., Sycara, K.: OWL-S: semantic markup for web services (2004)

  23. Martin, D.L., Burstein, M. H., McDermott, D.V., McIlraith, S.A., Paolucci, M., Sycara, K.P., McGuinness, D.L., Sirin, E., Srinivasan, N.: Bringing semantics to web services with OWL-S. World Wide Web 10(3), 243–277 (2007)

    Article  Google Scholar 

  24. Medjahed, B., Bouguettaya, A., Elmagarmid, A.: Composing web services on the semantic web. VLDB J. 12, 333–351 (2003)

    Article  Google Scholar 

  25. Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2/3), 161–180 (1995)

    MATH  MathSciNet  Google Scholar 

  26. Molloy, M., Reed, B.: The size of the largest component of a random graph on a fixed degree sequence. Comb. Probab. Comput. 7(3), 295–305 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  27. Newman, M.E.J.: Power laws, pareto distributions and Zipf’s law. Contemp. Phys. 46, 323–351 (2005)

    Article  Google Scholar 

  28. Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev., E 64(2), 026118 (2001)

    Article  Google Scholar 

  29. OASIS: UDDI—online community for the universal description, discovery, and integration (2008)

  30. Paolucci, M., Kawmura, T., Payne, T., Sycara, K.: Semantic matching of web services capabilities. In: International Semantic Web Conference (ISWC), pp. 333–347 (2002)

  31. Sirin, E., Parsia, B., Hendler, J.: Template-based composition of semantic web services. In: AAAI Fall Symposium on Agents and the Semantic Web (2005)

  32. W3C: Resource description framework. http://www.w3.org/RDF/ (2009)

  33. W3C: Web services description language (WSDL) version 2.0 part 1: core language. http://www.w3.org/TR/wsdl20/ (2007)

  34. W3C: The web ontology language. http://www.w3.org/TR/owl-features/ (2004)

  35. W3C: SOAP—simple object access protocol. http://www.w3.org/TR/soap12-part1/ (2007)

  36. Wang, Y., Stroulia, E.: Semantic structure matching for assessing web service similarity. In: IEEE International Conference on Services Computing (SCC), pp. 194–207 (2003)

  37. Watts, D.J.: The Dynamics of Networks between Order and Radnomness. Princeton University Press, Princeton (1999)

    Google Scholar 

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

    Article  Google Scholar 

  39. Wilf, H.S.: Generatingfunctionology, 2nd edition. Academic, London (1994)

    Google Scholar 

  40. Wu, J., Wu, Z.: Similarity-based web service matchmaking. In: IEEE International Conference on Services Computing (SCC), pp. 287–294 (2005)

  41. Zhang, J., Zhang, L.-J.: Web services quality testing. Int. J. Web Serv. Res. 2(2), 1–4 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Pennsylvania State University, University Park, 16802, PA, USA

    Hyunyoung Kil, Wonhong Nam & Dongwon Lee

  2. General Motors Corporation, Detroit, MI, USA

    Seog-Chan Oh

  3. Yahoo, Inc., Sunnyvale, CA, USA

    Ergin Elmacioglu

Authors
  1. Hyunyoung Kil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Seog-Chan Oh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ergin Elmacioglu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wonhong Nam
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Dongwon Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wonhong Nam.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kil, H., Oh, SC., Elmacioglu, E. et al. Graph Theoretic Topological Analysis of Web Service Networks. World Wide Web 12, 321–343 (2009). https://doi.org/10.1007/s11280-009-0064-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11280-009-0064-6

Keywords