Formal Concept Analysis of Social Networks

Social network analysis (SNA) typically appraises social groups by relying either on interaction patterns or on affiliation similarity. The former case represents the bulk of SNA approaches and relates to the so-called one-mode networks, which are by design blind to actor attributes. The latter case relates to what is denoted as two-mode networks and corresponds to a less abundant literature which uses actor attributes, yet eventually tends to focus much more on actor rather than attribute groups. This chapter aims to show how approaches such as formal concept analysis (FCA) make it possible to appraise actors and attributes on an equal footing. In the particular case of knowledge communities, where actor attributes represent cognitive properties, we deal with joint social and cognitive taxonomies, or socio-cognitive taxonomies. We further demonstrate that FCA also addresses several of the key traditional challenges of community detection in SNA—namely, overlapping groups, hierarchy, and temporal evolution and stability.

We consider individuality in bi-modal social networks, a facet that has not been considered before in the mathematical analysis of social networks. We use methods from formal concept analysis to develop a natural definition for individuality, and provide experimental evidence that this yields a meaningful approach for additional insights into the nature of social networks.

Subgroup discovery and community detection are standard approaches for identifying (cohesive) subgroups. This paper presents an organized picture of recent research in descriptive community (and subgroup) detection. Here, it summarizes approaches for the identification of descriptive patterns targeting both static and dynamic (sequential) relations. We specifically focus on attributed graphs, i.e.,complex relational graphs that are annotated with additional information. This relates to attribute information, for example, assigned to the nodes and/or edges of the graph. Combining subgroup discovery and community detection, we also summarize an efficient and effective approach for descriptive community detection.

Multimodal clustering is an unsupervised technique for mining interesting patterns in n-adic binary relations or n-mode networks. Among different types of such generalised patterns one can find biclusters and formal concepts (maximal bicliques) for two-mode case, triclusters and triconcepts for three-mode case, closed n-sets for n-mode case, etc. Object-attribute biclustering (OA-biclustering) for mining large binary datatables (formal contexts or two-mode networks) arose by the end of the last decade due to intractability of computation problems related to formal concepts; this type of patterns was proposed as a meaningful and scalable approximation of formal concepts. In this paper, our aim is to present recent advance in OA-biclustering and its extensions to mining multi-mode communities in SNA setting. We also discuss connection between clustering coefficients known in SNA community for one-mode and two-mode networks and OA-bicluster density, the main quality measure of an OA-bicluster. Our experiments with two-, three-, and four-mode large real-world networks show that this type of patterns is suitable for community detection in multi-mode cases within reasonable time even though the number of corresponding n-cliques is still unknown due to computation difficulties. An interpretation of OA-biclusters for one-mode networks is provided as well.

The Web Ontology Language (OWL) has gained serious attraction since its foundation in 2004, and it is heavily used in applications requiring representation of as well as reasoning with knowledge. It is the language of the Semantic Web, and it has a strong logical underpinning by means of so-called Description Logics (DLs). DLs are a family of conceptual languages suitable for knowledge representation and reasoning due to their strong logical foundation, and for which the decidability and complexity of common reasoning problems are widely explored. In particular, the reasoning tasks allow for the deduction of implicit knowledge from explicitly stated facts and axioms, and plenty of appropriate algorithms were developed, optimized, and implemented, e.g., tableaux algorithms and completion algorithms. In this document, we present a technique for the acquisition of terminological knowledge from social networks. More specifically, we show how OWL axioms, i.e., concept inclusions and role inclusions in DLs, can be obtained from social graphs in a sound and complete manner. A social graph is simply a directed graph, the vertices of which describe the entities, e.g., persons, events, messages, etc.; and the edges of which describe the relationships between the entities, e.g., friendship between persons, attendance of a person to an event, a person liking a message, etc. Furthermore, the vertices of social graphs are labeled, e.g., to describe properties of the entities, and also the edges are labeled to specify the concrete relationships. As an exemplary social network we consider Facebook, and show that it fits our use case.

We consider attribute pattern mining in an attributed graph through recent developments of Formal Concept Analysis. The core idea is to restrain the extensional space, i.e., the space of possible pattern extensions in the vertex set O, to vertex subsets satisfying some topological property. We consider two levels. At the abstract level, we reduce the extension of each pattern in such a way that the corresponding abstract extension induces a subgraph whose nodes satisfy some connectivity property. At the local level a pattern has various extensions each associated with a connected component of the abstract subgraph associated with the pattern. We obtain that way abstract closed patterns and local closed patterns, together with abstract and local implications. Furthermore, working at abstract and local levels leads to proper interestingness measures that evaluate to what extent patterns and implications are related to the topological information. Finally, we relate local concepts to network communities and show that to plainly express such a notion it may be necessary to apply our methodology to a new graph derived from the original network. We consider in particular the detection and ordering of k-communities in subgraphs of an attributed network.

In this paper we try to analyse the dual-projection approach to weighted 2-mode networks using the tools of\(\mathcal{K}\)-Formal Concept Analysis (\(\mathcal{K}\)-FCA), an extension of FCA for incidences with values in a particular kind of semiring.

For this purpose, we first revisit the isomorphisms between 2-mode networks with formal contexts. In the quest for similar relations when the networks have non-Boolean weights, we relate the dual-projection method to both the Singular Value Decomposition and the Eigenvalue Problem of matrices with values in such algebras, as embodied in Kleinberg’s Hubs and Authorities (HITS) algorithm.

To recover a relation with multi-valued extensions of FCA, we introduce extensions of the HITS algorithm to calculate the influence of nodes in a network whose adjacency matrix takes values over dioids, zerosumfree semirings with a natural order. In this way, we show the original HITS algorithm to be a particular instance of the generic construction, but also the advantages of working in idempotent semifields, instances of dioids.

Subsequently, we also make some connections with extended\(\mathcal{K}\)-FCA, where the particular kind of dioid is an idempotent semifield, and provide theoretical reasoning and evidence that the type of knowledge extracted from a matrix by one procedure and the other are different.