The analysis of social and complex networks with the assistance of graph theoretical methods has become fashionable. The authors of this paper apply existing analysis techniques to the semantic annotation of web services, by annotating the web services description languages (WSDLs) that syntactically describe web services. The paper is accessible to a large audience and is self-contained, as the authors provide the necessary mathematical and theoretical background for its understanding. The main result of this research is the development of a formal mapping of heterogeneous web services with annotations to bigraphs (service operation, entity attribute node), together with a set of algorithms for carrying out the transformation.

Two types of algorithms are proposed, based on matchmaking between elements of WSDLs on syntactic and on semantic attributes. Based on the explored relationships, a semantic network/graph is built. For the empirical study, two subject areas are selected, and the actual syntactic and semantic links, with the assistance of relevant ontologies, are transformed into an appropriate graph representation. The graph representation allows the statistical analysis of the created graphs to be performed and their behaviors investigated. The metrics or characteristics that are used for the evaluation of complex networks are the following: small-worldness, scale-freeness, and correlation degree on nodes. The evaluation uses a baseline annotations network against the automatically generated annotations that were created by the algorithms proposed in the paper. The accuracy of pairwise semantic matching between annotated elements is assessed using the F-measure.

One of the results of this study is that the networks of web services (WSDLs) can be considered as complex networks, and they show similar behaviors to other types of networks, such as technological networks, namely small-world properties, and scale-free and negative correlation degrees of nodes.

Another outcome of the study is that a proposed annotation mechanism for real-world web services is evaluated. The investigation demonstrated that the suggested mapping algorithms of semantic attributes preserve the significant characteristics of web services’ networks.

The paper is interesting for researchers who work on complex and social networks, web services, and the semantic web.