Towards Discovery of Subgraph Bisociations
2012, Nagel, Uwe, Thiel, Kilian, Kötter, Tobias, Piatek, Dawid, Berthold, Michael R.
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, domaincrossing relations based purely on structural properties of a relational knowledge description.
Network ensemble clustering using latent roles
2010, Brandes, Ulrik, Lerner, Jürgen, Nagel, Uwe
We present a clustering method for collections of graphs based on the assumptions that graphs in the same cluster have a similar role structure and that the respective roles can be founded on implicit vertex types. Given a network ensemble (a collection of attributed graphs with some substantive commonality), we start by partitioning the set of all vertices based on attribute similarity. Projection of each graph onto the resulting vertex types yields feature vectors of equal dimensionality, irrespective of the original graph sizes. These feature vectors are then subjected to standard clustering methods. This approach is motivated by social network concepts, and we demonstrate its utility on an ensemble of personal networks of migrants, where we extract structurally similar groups and show their resemblance to predicted acculturation strategies.
Analysis of Network Ensembles
2011, Nagel, Uwe
Subject of this dissertation is the assessment of graph similarity. The application context and ultimate aim is the analysis of network ensembles, i.e. collections of networks, in the sense of identifying structure among them, e.g. groups of highly similar networks. Structure is in this context understood as some form of regularity or description of the similarities among the considered networks.
As an illustration, consider a collection of two types of networks, where networks of the same type are very similar, while networks of different types are very dissimilar. These two groups form some kind of similarity that is of interest when the ensemble is the object to be analyzed.
Consequently, graphs are in this situation the elementary entities and the main interest is the measurement of structural similarities between them.
The interest in graphs as opposed to e.g. vectors as basic objects is motivated by their descriptive capabilities: some objects, e.g. electric circuits, social networks, comprehend important structural properties that can be expressed directly by modeling them as graphs. They have also found to be a powerful description mechanism for objects that do not incorporate an obvious relational structure as for example in image recognition.
Using graphs to describe objects leads to sets or collections of graphs on which problems of supervised and unsupervised learning are to be solved. A fundamental prerequisite in such approaches is the ability to compare the elementary objects, i.e. assess similarity or dissimilarity between them. For a number supervised and unsupervised learning algorithms a similarity or distance on the objects of analysis is even the sole prerequisite for their application, a prominent example given by support vector machines (c.f.Vapnik(1998)). Motivated by these considerations, three approaches for assessing and measuring similarity between graphs are developed.
Recognizing modes of acculturation in personal networks of migrants
2010, Brandes, Ulrik, Lerner, Jürgen, Lubbers, Miranda J., McCarty, Chris, Molina, José Luis, Nagel, Uwe
An individual's personal network encodes social contacts as well as relations among them. Personal networks are therefore considered to be characteristic and meaningful variables of individuals supplementing more traditional characteristics such as age, gender, race, or job position.
We analyze an ensemble of several hundred personal networks of migrants using a recently introduced classification method. As a result, individuals are partitioned into groups defined by similarity of their personal networks, and abstract summaries of classes are obtained. From the analysis we can conclude that Berry's modes of acculturation feature prominently in the empirical data.
Bisociative Discovery of Interesting Relations between Domains
2011, Nagel, Uwe, Thiel, Kilian, Kötter, Tobias, Piatek, Dawid, Berthold, Michael R.
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 can otherwise not be accomplished. 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.
Pure spreading activation is pointless
2009, Berthold, Michael R., Brandes, Ulrik, Kötter, Tobias, Mader, Martin, Nagel, Uwe, Thiel, Kilian
Almost every application of spreading activation is accompanied by its own set of often heuristic restrictions on the dynamics. We show that in constraint-free scenarios spreading activation would actually yield query-independent results, so that the specific choice of restrictions is not only a pragmatic computational issue, but crucially determines the outcome.