Semi-metric knowledge networks: applications to information retrieval and social data-mining

Luis Rocha
Indiana University

Given the ubiquitous presence of the Web in our lives, much of our knowledge and social foraging is done online, allowing us produce large-scale characterizations of the geometry of information exchanges and social interactions in human societies. Most interactions in the knowledge and social space we live were found to be well described in terms of complex networks. The majority of research on complex networks, however, treats interactions as binary edges in graphs, even though interactions in real networks exhibit a wide range of intensities or strengths. Therefore, there is still much to do to bring decades of research on weighted graphs to bear on the field of complex networks. One field, in particular, that has accumulated substantial knowledge about weighted graphs is the field of Fuzzy Set Theory.

While the Fuzzy Set community has focused extensively on the mathematical characteristics of weighted graphs and how to manipulate them, it has not focused much on the structure and dynamics of real networks obtained from empirical data. For instance, we show that the most common form of transitive closure in Fuzzy Graphs destroys the scale-free structure of complex networks. Conversely, the complex networks community has paid very little attention to the mathematics of weighted graphs. For instance, the very intuitive metric closure of distance graphs has very poor axiomatic features.

We have been working towards bridging and advancing these two distinct communities, on the topic of transitivity in weighted graphs as models of real-world networks---specifically knowledge networks extracted from Web-related technology. The concept of transitive closure is important because it allows us to identify indirectly related items and coherent cliques in a network. This has useful applications in recommender systems, literature mining, information retrieval, and social network modeling. However, unlike standard graphs, in weighted graphs there is an infinite number of ways to compute transitive closures. Therefore, we need to understand which ones preserve important characteristics of real networks and observe good axiomatic requirements. We present a transitive closure which is axiomatically sound, behaves very similarly to the metric closure, and tends to preserve scale-free structure. We discuss its application in recommender systems, information retrieval, and social data mining.

Presentation (PDF File)

Back to Workshop III: Social Data Mining and Knowledge Building