Search

The integration of heterogeneous data from various domains without the need for prefiltering prepares the ground for bisociative knowledge discoveries where attempts are made to find unexpected relations across seemingly unrelated domains. Information networks, due to their flexible data structure, lend themselves perfectly to the integration of these heterogeneous data sources. This chapter provides an overview of different types of information networks and categorizes them by identifying several key properties of information units and relations which reflect the expressiveness and thus ability of an information network to model heterogeneous data from diverse domains. The chapter progresses by describing a new type of information network known as bisociative information networks. This kind of network combines the key properties of existing networks in order to provide the foundation for bisociative knowledge discoveries. Finally based on this data structure three different patterns are described that fulfill the requirements of a bisociation by connecting concepts from seemingly unrelated domains.

Diese Arbeit befasst sich mit der Durchsuchung von Netzwerken mittels Aktivierungsausbreitungsverfahren. Netzwerke, formell oft als Graphen dargestellt, sind Datensätze bestehend aus Datenobjekten (Knoten) und Beziehungen zwischen diesen (Kanten). In vielen Bereichen, wie z.B. Information Retrieval, werden Netzwerke bezüglich bestimmter Anfragen nach in Beziehung stehenden, relevanten oder interessanten Datenobjekten durchsucht. Unter anderem werden dazu Aktivierungsausbreitungsverfahren eingesetzt. In diesen Verfahren werden die Knoten, welche die Datenobjekte der Anfrage repräsentieren, initial aktiviert. Die Aktivierung jedes Knotens breitet sich iterativ über verbundene Kanten zu benachbarten Knoten aus, wobei diese ebenfalls zu einem bestimmten Grad aktiviert werden. Das finale Aktivierungsniveau nach einer bestimmten Anzahl an Iterationen wird als heuristisches Maß für Relevanz, Interessantheit oder Wichtigkeit etc. interpretiert. Als Ergebnis auf eine Anfrage werden die Datenobjekte nach ihrem Aktivierungsniveau sortiert aufgelistet.Unbeschränkte Aktivierungsausbreitungsverfahren haben jedoch verschiedene Nachteile, weshalb bisher meist heuristische Beschränkungen zum Einsatz gekommen sind, um diese zu vermeiden. In dieser Arbeit wird ein weiterer Nachteil, die Konvergenz zu einem anfrageunabhängigen Fixpunkt, gezeigt sowie Verfahren zur Vermeidung dieses Nachteils beschrieben, die ohne den Einsatz von Beschränkungen auskommen.Des Weiteren wird gezeigt, wie auf Basis der Konvergenz zwei Arten von Ähnlichkeiten zwischen Knoten in Graphen aus Aktivierungsausbreitungsprozessen bestimmt werden können. Durch die Sortierung der Knoten bezüglich beider Ähnlichkeiten zu Anfrageknoten ergeben sich, zusätzlich zur Sortierung aufgrund ihres Aktivierungsniveaus, weitere Möglichkeiten Netzwerke zu durchsuchen.Die Aktivierungsähnlichkeit basiert auf der Überlappung der direkten und indirekten Nachbarschaft zweier Knoten und ist eine Relaxierung der maximalen strukturellen Äquivalenz. Je stärker die Überlappung, desto höher ist der Grad der Ähnlichkeit zweier Knoten. Zwei Knoten, die einen hohen Grad an Ähnlichkeit aufweisen, müssen demnach im Graphen eine geringe Distanz haben, was eine Einschränkung der Möglichkeiten zur Durchsuchung anhand der Aktivierungsähnlichkeit bedeutet. Diese Ähnlichkeit ist geeignet um dichte umgebende Teilgraphen oder Knotengemeinschaften, um Anfrageknoten zu extrahieren.Die Signaturähnlichkeit basiert auf dem Vergleich der Struktur der direkten und indirekten Nachbarschaft zweier Knoten, nicht auf der Überlappung dieser. Es wird gezeigt, dass Knoten, die strukturell nicht unterschieden werden können, also automorphe Abbilder voneinander sind, stets maximal ähnlich sind. Die Signaturähnlichkeit ist eine Relaxierung der maximalen Orbit-Äquivalenz und ein heuristisches Maß für die strukturelle Ähnlichkeit der Nachbarschaft von Knoten. Zwei Knoten, die einen hohen Grad an Ähnlichkeit aufweisen, müssen im Graphen nicht notwendigerweise eine geringe Distanz haben, sondern können sich weit entfernt voneinander befinden. Dies ist bei der Aktivierungsähnlichkeit bzw. beim Aktivierungsniveau nicht der Fall und eröffnet neue Möglichkeiten beim Durchsuchen von Netzwerken mittels Aktivierungsausbreitung.Anhand von künstlichen Daten werden bestimmte Eigenschaften beider Ähnlichkeiten empirisch überprüft. Des Weiteren werden zwei Netzwerke mit unterschiedlicher Struktur, bestehend aus realen Daten, anhand beider Ähnlichkeiten durchsucht. Dabei werden beispielhaft die Nachbarschaften und Knotengemeinschaften von Knoten mit hoher Signaturähnlichkeit mit geeigneten Layoutverfahren visualisiert, um strukturelle Kohärenzen zu zeigen.

The discovery of surprising relations in large, heterogeneous information repositories is gaining increasing importance in real world data analysis. If these repositories come from diverse origins, forming different domains, domain bridging associations between otherwise weakly connected domains can provide insights into the data that are not accomplished by aggregative approaches. In this paper, we propose a first formalization for the detection of such potentially interesting, domain-crossing relations based purely on structural properties of a relational knowledge description.

Konzepte spielen in unserem täglichen Leben eine wichtige Rolle, wenn auch nur unbewusst.So gruppieren Konzepte Objekte mit gemeinsamen Eigenschaften und ermöglichen uns das Abstrahieren und Kommunizieren von bestehendem Wissen sowie die Verarbeitung der pausenlos auf uns einströmenden Flut von Informationen.Dabei agiert ein Konzept als Repräsentant seiner Mitglieder und ihrer gemeinsamen Eigenschaften.Wenn wir an das Konzept der Transportmittel denken, fallen uns spontan einige Mitglieder und ihre Eigenschaften ein, die diese als Transportmittel auszeichnen.Eine weitere Besonderheit der Konzepte ist, dass ein Objekt Mitglied in scheinbar unabhängigen Konzepten sein kann.So gilt ein Auto sowohl als Transportmittel als auch als Luxusgegenstand.Der in dieser Arbeit beschriebene Ansatz macht sich diese Leistungsfähigkeit und Flexibilität von Konzepten zunutze, um das kreative Denken zu fördern.So ermöglicht der Ansatz das Finden von existierenden sowie unbekannten Konzepten in heterogenen Daten, welche das Verständnis für komplexe Systeme fördern sowie interessante und unerwartete Zusammenhänge aufdecken.Da bei der Suche nach unerwarteten Zusammenhängen nicht von Anfang an feststeht, wonach man eigentlich sucht, sollte bei der Integration der zur Verfügung stehenden Daten möglichst keine Information verloren gehen.Daher basiert der beschriebene Ansatz auf Informationsnetzwerken, welche dank ihrer flexiblen Datenstruktur die Integration von Daten unterschiedlichster Beschaffenheit und Qualität unterstützen.So speichern Informationsnetzwerke die Informationen in Form von Beziehungen zwischen Objekten in einer Graphstruktur, wobei Objekte als Knoten und ihre Beziehungen als Kanten im Graphen repräsentiert werden.Basierend auf dieser Datenrepräsentation beruht der beschriebene Ansatz auf der Annahme, dass Objekte durch ihre direkten Nachbarn im Netzwerk beschrieben werden.Somit bilden ähnliche Objekte und ihre gemeinsamen Nachbarn einen quasi bipartiten Graphen.Dieser aus den beiden Knotenpartitionen und ihren Verbindungen bestehende Teilgraph bildet die Basis des beschriebenen Ansatzes, den sogenannten Konzeptgraphen.Die Güte der Verbindungen zwischen den beiden Knotenpartitionen wird mithilfe einer Gütefunktion bestimmt, welche das Fehlen einzelner Verbindungen bestraft.Daher sollten sich die ähnlichen Objekte möglichst viele Nachbarn teilen.Einen Spezialfall stellen dabei die vollständigen Konzeptgraphen dar, deren Knotenpartitionen vollständig verbunden sind.Zum Klassifizieren der Knoten eines Konzeptgraphen werden ferner Heuristiken basierend auf der Graphstruktur vorgestellt, welche die Identifizierung der Mitglieder und Eigenschaften eines Konzeptes sowie des Konzeptrepräsentanten ermöglichen.Dabei ist der Typ eines Knotens kontextabhängig und kann so in unterschiedlichen Konzeptgraphen variieren.Die Heuristik zur Bestimmung des Konzeptrepräsentanten liefert darüber hinaus ein Maß für dessen Güte, welches zum Auffinden eines fehlenden Repräsentanten verwendet werden kann.Ein fehlender Konzeptrepräsentant kann dabei ein Anzeichen für unvollständige und verrauschte Daten sein.Er kann aber auch ein Hinweis auf eine Gruppe von Objekten mit gemeinsamen Eigenschaften sein, die bisher noch nicht entdeckt wurden und daher noch keinen Konzeptrepräsentanten besitzen.Neben der Formalisierung von Konzeptgraphen werden Verfahren zum Finden von vollständigen Konzeptgraphen sowie Ansätze zum Finden von allgemeinen Konzeptgraphen beschrieben.Die beschriebenen Verfahren und Ansätze basieren auf existierenden Verfahren zum Finden von Frequent Item Sets, welche sich durch die Konvertierung des Graphen in eine Transaktionsliste anwenden lassen.Fallstudien demonstrieren schließlich die Existenz sowie die Flexibilität und Vielfältigkeit von Konzeptgraphen anhand von zwei unterschiedlichen Datensätzen aus der realen Welt.So basiert der erste Datensatz auf einer Enzyklopädie mit Artikeln aus unterschiedlichen Wissensgebieten.Der zweite Datensatz basiert hingegen auf strukturierten sowie unstrukturierten Informationen über Medikamente.In beiden Datensätzen werden sinnvolle Konzeptgraphen mithilfe des beschriebenen Verfahrens zum Finden von vollständigen Konzeptgraphen gefunden und ihre Knoten unter Verwendung der vorgestellten Heuristiken in die unterschiedlichen Typen eingeteilt.Basierend auf dem Gütewert für den Konzeptrepräsentanten werden ferner Konzeptgraphen ohne sinnvollen Repräsentanten identifiziert, welche unbekannte Zusammenhänge aufdecken.Überlappende Konzeptgraphen demonstrieren schließlich die volle Flexibilität und Vielfältigkeit von Konzeptgraphen.So können die Überlappungen sowohl zum Identifizieren von Hierarchien verwendet werden als auch zu einem besseren Verständnis komplexer Zusammenhänge führen.Darüber hinaus ermöglichen sie auch das Auffinden fehlender Verbindungen, die zu neuen Erkenntnissen führen.Durch die Verwendung von Informationsnetzwerken als Eingabedaten und dem Auffinden von existierenden sowie unbekannten Konzepten unterstützt das in dieser Arbeit vorgestellte Verfahren das kreative Denken, indem es sowohl das Verständnis komplexer Systeme fördert als auch interessante und unerwartete Zusammenhänge aufdeckt.

In this paper we propose two methods to derive two different kinds of node similarities in a network based on their neighborhood. The first similarity measure focuses on the overlap of direct and indirect neighbors. The second similarity compares nodes based on the structure of their - possibly also very distant - neighborhoods. Instead of using standard node measures, both similarities are derived from spreading activation patterns over time. Whereas in the first method the activation patterns are directly compared, in the second method the relative change of activation over time is compared. We apply both methods to a real-world graph dataset and discuss the results.

The thesis is an area study focusing on Japanese business associations in the sector of information- and communication technologies (ICT) and the chemical industry. It applies the general perspective that business associations are embedded actors within specific social and political contexts. It also explains the challenges of globalisation and regionalisation for business associations. And empirically shows how they perceive and strategically react on these challenges. With the help of new theoretical approaches and network analysis the institutionalised structure of exchange between firms, business associations and the state are analysed. The analysis places special emphasis on personal exchange-structures (jinmyaku) like shukko and amakudari. As a meta-theoretical framework, institutionalism is applied at the macro-level. At the meso-level the external and internal organisational environment is explained in the framework of the logic of membership and the logic of influence. The relations between the associations are visualised and explained with the tool network analysis. The micro-level analysis explains the outcome of the network structures while focusing on the specific role of socialisation and embedded norms and traditions. Hence, the education system in Japan plays a central role and also social relations are of high importance. This constructs a common base of orientations and norms and therefore makes social interaction easier. One characteristic of the Japanese associational system is great number of so called niche associations. As a result consolidation processes are more likely mergers between national associations and niche associations then cut-throat competition. Within the ict-sector there are still more adaption processes then in the already established chemical sector. Consequently chemical associations do not face due to economic and technical changes a high risk of competition. At the national level stable bargaining networks have been established. Chemical industry associations are more independent from state actors then ict-associations. Nevertheless, in both branches personalised network structures are seen as a determining factor for the understanding of decision-making processes in Japan.

Since the mid-1970s, the quantitative literature on political networks has grown to approximately 200 publications. A number of scholars have recently tried to organize the "Babylonian variety" of different policy network concepts and schools of thought in political network analysis. It will be demonstrated that they fail to grasp the important distinctions between the research specialties, and an empirical assessment of the quantitative literature is offered by analyzing co-citation data and data of bibliographic coupling.The similarity between any pair of citing publications is determined by the number of citations these publications have in common, and the similarity between any two cited articles is shaped by the number of common citing bibliographies. A 193x8490 affiliation matrix containing the links between citing and cited documents is transformed into two square adjacency matrices and then examined separately by means of multivariate data analysis and Social Network Analysis. Using clique analysis, cluster analysis and blockmodels in conjunction with multidimensional scaling and correspondence analysis, the important schools of thought can be identified as clusters in an n-dimensional space. Once the clusters have been delineated on the level of cited publications, the citing documents can be classified and a likelihood distribution for each publication of belonging into any school of thought can be given.The results show that four large clusters can be separated and interpreted in a meaningful way in terms of research design, topic, use of methods and some other characteristics. These schools of thought are preliminarily called "exchange cluster", "governance cluster", "elite cluster" and "participation cluster". Results are discussed in the light of Crane s invisible-colleges framework and other approaches from the sociology of science as well as recent theoretical contributions to the study of policy networks.The citation-based analysis of the discipline is complemented by an analysis of the methods and relations used in the citing documents and their distributions of actors, countries, levels of analysis and areas of inquiry examined.

We present suitable design patterns and basic algorithms and use them to discuss the computation of popular network indices. With methods from discrete statistics, we are able to visualize and summarize these results for large networks. Furthermore, we talk about heuristic speed-up and approximation techniques to handle even networks that are too large to get the correct results in an acceptable time.

Deutsche auswärtige Kulturpolitik ist ein Thema, das in der Öffentlichkeit auf recht geringes Interesse stößt. Doch auch hier machen sich die zunehmenden Sparmaßnahmen bemerkbar. Die Arbeit untersucht, wie die einzelnen Mittlerorganisationen auf die Kürzungen reagieren. Dabei ist hauptsächlich die Kooperation untereinander und die Zusammenarbeit mit der Privatwirtschaft von Interesse. Neben diesem Vergleich der einzelnen Organisationen sollen auch die Netzwerke einander gegenübergestellt werden, die diese Organisationen im jeweiligen Gastland aufbauen. Es wird davon ausgegangen, daß die Institutionen sich in gewissem Maß in das politischen System des Gastlandes einbetten. Die beiden Staaten USA und Großbritannien bieten sich hier besonders für einen Vergleich an. Die Ergebnisse basieren auf einer Befragung der offiziellen Mittlerorganisationen und einiger bilateraler Organisationen anhand von Fragebögen.

One goal in network design is the construction of sparse networks that guarantee short distances with respect to some given distance requirements. By this, it can be guaranteed, for example, that delays that are incurred by link faults are bounded. An appropriate graph-theoretic model for this is the concept of k-spanners: Given a graph G, a k-spanner of G is a spanning subgraph S, such that the distance between any two vertices in S is at most k times longer than the distance in G. Research in this area has mainly concentrated on two aspects: minimum k-spanners, i.e., k-spanners that contain the fewest edges among all k-spanners, and tree k-spanners, i.e., spanners that are trees. In this thesis, we use k-spanners to model further desirable properties from network design (such as reliability) within a graph-theoretic framework. Our main emphasis is on sparse graphs that guarantee short distances, and we are interested in simple structures and fault-tolerance.