Understanding and analysing rapidly changing and growing business ecosystems, like smart city and mobility ecosystems, becomes increasingly di cult. However, the understanding of these ecosystems is the key to being successful for all involved parties, like companies and public institutions. Modern Natural Language Processing technologies can help to automatically identify and extract relevant information from sources like online news and blog articles and hence support the analysis of complex ecosystems. In this paper, we present an approach to automatically extract directed relations between entities within business ecosystems from online news and blog articles by using dependency parsing.
Digitization - and its advancements - has long reached cities including their
outskirts and rural satellites and is changing urban mobility. Cities are transforming
into Smart Cities, whereby Smart Mobility is often recognized among the most
common indicators of Smart Cities [
Established mobility actors, such as automotive OEMs, their Tier 1 to 3
parts supplier, but also public transportation agencies, are challenged especially
by technology companies using their advantage of applying new technologies
- such as augmented reality or arti cial intelligence - to urban mobility. Tech
giants such as Google and Apple are entering the mobility scene by developing
self-driving cars and pushing autonomous driving [
Besides commercial mobility providers, also cities, their public institutions, and their governments are under pressure to address these challenges and to understand the emerging structures within mobility ecosystems to make informed decisions [10].
Thereby, ecosystem data is large and heterogeneous [
The manual collection and extraction of the data can be considered as a time-consuming and tedious work providing a noticeable limitation for the datadriven analysis of the business ecosystem. An automation of this process could not only save valuable resources but could also enable (almost) real-time availability of the data and hence create possibilities for more advanced analyses of changes within an ecosystem and foster more advanced Arti cial Intelligence (AI) systems, which could not only be useful for actors within the ecosystem, but also e.g. for nancial analysts.
The here presented research is part of a smart city initiative pursued by a European city. Within this paper, we present an approach to automatically extract directed relations about actors within smart city ecosystems from internet news and blog articles by using dependency trees. We present and evaluate a prototypical implementation of this approach, combining machine learning methods (for dependency parsing) and rule-based approaches (for relation direction extraction). Such a system could in the future be used in combination with visualisation tools, in order to foster the manual analysis of such ecosystems by humans, or with AI systems, in order to enable a more automated and data-driven analysis. 2
A very popular eld of application for relation extraction is bioinformatics, where
the relation between genes and proteins is extracted from scienti c publication.
Often, kernel methods are used to achieve this goal, e.g. by [17], [14], [
Lee et al. [13] used convolutional neural networks to extract the directed relations \hypnoym of" and \synonym of" from scholarly articles. In their evaluation, they achieved an F1 score of 0.645.
Fundel et al. [7] presented an approach which is very similar to the approach we present in this paper. They used named entity recognition (NER) and dependency trees in order to extract relations. However, in the domain of proteins and genes, NER is a much easier task compared to names of companies and institutions, which often consist of \regular" words. Moreover, they just extracted two types of relations: A activates B (and its inversion) and A interacts with B. In smart city ecosystems, there are much more di erent types of relation which could be of interest.
Yamamoto et al. [21] used the DeepDive system [22] to extract relations between companies in the semiconductor industry from web news articles. However, they only focused on undirected, high-level relations: collaboration and competition. The same two relations were also extracted by Lau and Zhang [12] by using a Support Vector Machine. While they achieved an F1-score of 0.868 when it comes to business entity identi cation, for the relation extraction they only achieved an F1-score of 0.625 (collaboration) respectively 0.631 (competition).
Both approaches work with English texts. In contrast, we work with texts in German language and want to extract more ne-grained, directed relations. 3
In this paper, we want to focus on three important relations which describe the constitution of smart city ecosystems and more broadly business ecosystem in general: \owns", \funds", and \cooperation".
While the rst two of these relations are directed (i.e. A owns B =6 ) B owns A), the relation cooperation is not directed (i.e. A cooperation B =) B cooperation A). In order to evaluate our approach, we manually collected a dataset of 41 news and blog articles that contain information about one of the above-mentioned relation between two companies from the smart city ecosystem and manually annotated it on a document level. The sources from which the articles were extracted include major German news outlets (like \Welt"1 or 1 https://www.welt.de \Handelsblatt"2) as well as small niche blogs (like \eMobilitaet"3). Every article was annotated by two persons with a consensual annotation. Figure 1 shows the distribution of the three relations within the collected dataset. Table 1 shows the companies which are included in the dataset along with the number of relations they occur in.
owns
15 12 funds 14 cooperation In order to automatically extract relations from online news and blog articles, a set of preprocessing steps has to be conducted rst. For this, we use a pipes and lters architecture [15], which is shown in Figure 2. In a rst step, we extract the main article content from the website by removing unrelated elements like the header, navigation or footer by using the boilerpipe Java library4, which uses shallow text features to separate the main content from the other structure. [11] Subsequently, HTML tags are stripped from the main content and the text is split into sentences. These sentences are the basis for the detection and extraction of the relations.
In order to avoid having to annotate huge sets of training data for each and
every type of relation, we decided to use a hybrid approach, combining machine
learning and manually crafted rules. We use the dependency parser developed by
Chen and Manning [
We then created rules which extract, based on the dependency trees, the relations we are interested in. Figure 3 shows, for example, the dependency graph for the sentence \Daimler und BMW kooperieren fur verbessertes CarsharingErlebnis." (Daimler and BMW cooperate for improved Carsharing-experience ). 2 https://www.handelsblatt.de 3 https://www.emobilitaetblog.de 4 https://boilerpipe-web.appspot.com/ company # company # company # In this sentence, we nd the undirected relation \cooperation" between the entities Daimler and BMW. In order to automatically detect relations, we rst check for each sentence whether it includes information about one of the relations we are looking for (owns, funds, cooperation). In order to do this, we de ne one or more keyword for each of the relations: e.g. \kooperiert" for cooperation, \investieren" for funds, and \ubernehmen" and \kauft" for owns. We stem each sentence using the Snowball stemmer5 and subsequently search for occurrences of the (stemmed) keywords or synonyms of them which we acquire through the Open Thesaurus API6.
Another advantage of our (partially) rule-based approach is the fact that it can easily be transferred to other languages by translating the identi ed keywords and using a di erent Thesaurus and model for the dependency parser.
In the case of the example in Figure 3, once we identi ed the token which de nes the type of the relation (\kooperieren"), it is su cient to look for the Named Entities (NE), i.e. nouns, which are subject to this token, hence we are looking for nsubj connections in the graph, which leads us to the tokens BMW and Daimler.
For the two other relations, owns and funds, rules can get a bit more complex, since both relations are directed and it is therefore not su cient to just 5 http://snowballstem.org/ 6 https://openthesaurus.de Menu
Article Lorem ipsum
Article Lorem ipsum 1 RROOOOTT JPeIDdAeT KdeütndNiNgung rmVoMoutFsINs sncsuhbArjDifJtDaluicxahd vmoderVfoVIlNgFen.
{ } e1: “Company 1”, relation: “owns”, e2: “Company 2” Content extraction
Dependency parsing
Relation extraction nsubj nmod punct Daimler/NE-1 nsubj
Carsharing-Erlebnis/NN-7 ./$.-8 cc conj:und case amod und/KON-2
BMW/NE-3 für/APPR-5 verbessertes/ADJA-6 identify the related entities, but it is also necessary to detect and extract the direction of the relation. The two sentences \Siemens ubernimmt niederlandisches Startup Tass." (Siemens acquires Dutch startup Tass.) and \Niederlandisches Startup Tass wird von Siemens ubernommen." (Dutch startup Tass is acquired by Siemens.) are basically identical, but one time the German verb \ubernehmen" (to acquire) is used in its active form and once in the passive form. However, this small di erence is very important for the direction of the relation.
One of the reasons why we choose an approach using dependency trees is their power when it comes to distinguishing the direction of a relation, as shown in Figure 4 and 5. In Figure 4, \Siemens" is the nominal subject (nsubj), hence, in the relation, \Siemens" is the company which acquired another company. Therefore, we just have to look for the second Named Entity in the sentence to get the full relation. In Figure 5, \Tass" is the passive nominal subject (nsubjpass), hence, it is clear that \Tass" is the company which was acquired by another company.
übernimmt/VVFIN-2 nsubj dobj xcomp punct Siemens/NE-1
Startup/NN-4
Tass/NE-5
./$.-6 amod niederländisches/ADJA-3
The same rules apply for the \funds" relation. In general, these are obviously just examples and not an exhaustive set of rules. The keyword can, for example, not only occur as a verb, like in the examples we gave before, but also in form of a noun, as shown in Figure 6 and Figure 7. We can again distinguish the direction of the relationship by looking at the nominal subject (nsubj, Figure 6) or passive nominal subject (nsubjpass, Figure 7) relation.
The rules we use in our prototype were developed based on an existing, handcrafted, database which contains more than 470 structured relations between companies from the smart city domain and links to the websites the information was (manually) extracted from. This database is distinct from the set described in Section 3 which we will use to evaluate our prototype. In addition to the three relations we focus on (owns, funds and cooperation), this database also includes the additional relations \supplied by" and \partially owns".
In order to make our prototype universally applicable and easy to integrate with existing tools, we decided to provide the functionality through a REST API. The prototype itself is, therefore, a standalone Java application. nmod
punct Tass/NE-3 wird/VAFIN-4
Siemens/NE-6
case von/APPR-5 dobj nmod punct hat/VAFIN-2 Übernahme/NN-4
Tass/NE-6 ./$.-8 nsubj det case Siemens/NE-1 die/ART-3 von/APPR-5 nmod punct Übernahme/NN-2 wurde/VAFIN-5
Siemens/NE-7 ./$.-9 det
nmod Die/ART-1
Tass/NE-4
case von/APPR-3
case durch/APPR-6 While the usage of manually crafted rules has some advantages, it also introduces some limitations. The success of the system is for example highly dependent on the quality of the thesaurus which is used. In this paper, we only look at a very small subset of relations which might be of interests for smart city ecosystems. Especially di erentiation between relations like \owns" and \partially owns" might prove to be di cult with the approach we choose. For some relations, it might even for humans be di cult to distinguish between them and not all relations are necessarily exclusive, like e.g. \supplied by" and \cooperates". Again, since we only look at a small subset of relations, we did not encounter any of these problems for our prototype. 6
In order to evaluate our approach, we used the dataset described in Section 3 with our prototype. We evaluated both, the extraction of the relation itself (i.e. whether the relations \owns", \ nances" or \cooperates" are extracted correctly) and the evaluation of the involved entities. For the directed relations, we also evaluated whether the direction of the relations was extracted correctly.
The results of the evaluation of the relation extraction are shown in Table 2. Overall, with an F1 score of 0.862 (unweighted average) the results look very promising, especially given the fact that we used a general-purpose thesaurus without any content specialised for the task we wanted to solve, and signi cantly outperform e.g. the results achieved by [12].
However, the relation extraction alone is not yet very meaningful. For the task we want to solve, it is also crucial that the right entities are extracted and, for the directed relations, also that they are extracted in the right order. For this evaluation, we were not only considering exact matches as correct but also variations, like \VW" for \Volkswagen" or \In neon" for \In neon Technologies". In production-use, these variations would need to be mapped in order to be unambiguous.
The results of this evaluation are shown in Table 3. Each of our relations contains two entities. In the evaluation, we distinguish whether no entity, one entity or both entities were extracted correctly, independent from their direction. Only in the column \correct direction" we distinguish whether the extracted direction was correct or not. If just one entity was extracted correctly, the direction is considered to be correct if this one entity is on the \right side" of the relation. For this evaluation, we only took into account the true positives identi ed in the previous evaluation.
Overall, the 35 correctly classi ed relations contained 70 entities. Out of this 70 entities, our prototype correctly extracted 50 entities and failed to extract 20 entities. During the evaluation, it was obvious that the standard NER we used from the Stanford Library is not optimal for the task. Even big company names like \Volkwagen" were, in some cases, not recognised as named entities. However, only in four out of 35 cases none of the involved entities could be extracted. In cases were at least one entity could be extracted, the direction of the relation was correctly extracted in 18 out of 19 cases.
Overall, our prototype performed very well, especially with regard to the extraction of relations and their direction, which distinguishes our prototype from most of the approaches presented in Section 2, which do not consider the direction of a relation. 7
In this paper, we presented an approach using dependency trees to automatically extract directed relations between companies from German news and blog articles in order to automatically analyse smart city ecosystems. With an F1 score of 0.862, our prototype was successful in detecting relations and with 94.74% correctly directed relations even more so with regard to the direction of detected relations. Currently, the main shortcoming of the system is the extraction of involved entities. While we were able to extract at least one of the involved entities correctly in 88.57% of the cases, both entities were extracted correctly only in 54.29% of all cases. In the future, this value could be improved by using more sophisticated methods for named entity recognition.
In the future, our prototype could be combined with visualisation tools, in
order to foster the manual analysis of such ecosystems by humans, or with AI
systems, in order to enable a more automated and data-driven analysis, using
the REST API we implemented.
7. Fundel, K., K ner, R., Zimmer, R.: Relexrelation
extraction using dependency parse trees. Bioinformatics 23(3),
365{371 (2007). https://doi.org/10.1093/bioinformatics/btl616,
http://dx.doi.org/10.1093/bioinformatics/btl616
8. Hao, J., Zhu, J., Zhong, R.: The rise of big data on urban studies and planning
practices in china: Review and open research issues. Journal of Urban Management
4(2), 92{124 (2015)
9. Iyer, B.R., Basole, R.C.: Visualization to understand ecosystems. Communications
of the ACM 59(11), 27{30 (2016)
10. Khatoun, R., Zeadally, S.: Smart cities: concepts, architectures, research
opportunities. Communications of the ACM 59(8), 46{57 (2016)
11. Kohlschutter, C., Fankhauser, P., Nejdl, W.: Boilerplate detection using shallow
text features. In: Proceedings of the third ACM international conference on Web
search and data mining. pp. 441{450. ACM (2010)
12. Lau, R., Zhang, W.: Semi-supervised statistical inference for business entities
extraction and business relations discovery. Balog et al.[