Can Entities be Friends?
Pereira Nunes, B.; Kawase, R.; Dietze, S.; Taibi, D.; Casanova, M. A. & Nejdl, W.
Rizzo, G.; Mendes, P.; Charton, E.; Hellmann, S. & Kalyanpur, A., ed., 'Proceedings of the Web of Linked Entities Workshop in conjuction with the 11th International Semantic Web Conference', 906(),, 45-57 (2012) [pdf]
The richness of the (Semantic) Web lies in its ability to link related resources as well as data across the Web. However, while relations within particular datasets are often well defined, links between disparate datasets and corpora of Web resources are rare. The increasingly widespread use of cross-domain reference datasets, such as Freebase and DBpedia for annotating and enriching datasets as well as document corpora, opens up opportunities to exploit their inherent semantics to uncover semantic relationships between disparate resources. In this paper, we present an approach to uncover relationships between disparate entities by analyzing the graphs of used reference datasets. We adapt a relationship assessment methodology from social network theory to measure the connectivity between entities in reference datasets and exploit these measures to identify correlated Web resources. Finally, we present an evaluation of our approach using the publicly available datasets Bibsonomy and USAToday.
A Classification-based Approach for Bibliographic Metadata Deduplication
Borges, E. N.; Becker, K.; Heuser, C. A. & Galante, R.
Proceedings of the IADIS International Conference WWW/Internet 2011 221-228 (2011) [pdf]
Digital libraries of scientific articles describe them using a set of metadata, including bibliographic references. These references can be represented by several formats and styles. Considerable content variations can occur in some metadata fields such as title, author names and publication venue. Besides, it is quite common to find references that omit same metadata fields such as page numbers. Duplicate entries influence the quality of digital library services once they need to be appropriately identified and treated. This paper presents a comparative analysis among different data classification algorithms used to identify duplicated bibliographic metadata records. We have investigated the discovered patterns by comparing the rules and the decision tree with the heuristics adopted in a previous work. Our experiments show that the combination of specific-purpose similarity functions previously proposed and classification algorithms represent an improvement up to 12% when compared to the experiments using our original approach.
Visit me, click me, be my friend: an analysis of evidence networks of user relationships in BibSonomy
Mitzlaff, F.; Benz, D.; Stumme, G. & Hotho, A.
, 'HT '10: Proceedings of the 21st ACM Conference on Hypertext and Hypermedia', ACM, New York, NY, USA, [10.1145/1810617.1810664], 265-270 (2010) [pdf]
The ongoing spread of online social networking and sharing sites has reshaped the way how people interact with each other. Analyzing the relatedness of different users within the resulting large populations of these systems plays an important role for tasks like user recommendation or community detection. Algorithms in these fields typically face the problem that explicit user relationships (like friend lists) are often very sparse. Surprisingly, implicit evidences (like click logs) of user relations have hardly been considered to this end. Based on our long-time experience with running BibSonomy [4], we identify in this paper different evidence networks of user relationships in our system. We broadly classify each network based on whether the links are explicitly established by the users (e.g., friendship or group membership) or accrue implicitly in the running system (e.g., when user u copies an entry of user v). We systematically analyze structural properties of these networks and whether topological closeness (in terms of the length of shortest paths) coincides with semantic similarity between users.
Mapping Bibliographic Records with Bibliographic Hash Keys
Voss, J.; Hotho, A. & Jäschke, R.
Kuhlen, R., ed., 'Information: Droge, Ware oder Commons?', Proceedings of the ISI, Verlag Werner Hülsbusch (2009) [pdf]
This poster presents a set of hash keys for bibliographic records called bibkeys. Unlike other methods of duplicate detection, bibkeys can directly be calculated from a set of basic metadata fields (title, authors/editors, year). It is shown how bibkeys are used to map similar bibliographic records in BibSonomy and among distributed library catalogs and other distributed databases.
Detecting Commmunities via Simultaneous Clustering of Graphs and Folksonomies
Java, A.; Joshi, A. & Finin, T.
, 'WebKDD 2008 Workshop on Web Mining and Web Usage Analysis' (2008)
Modularity and community detection in bipartite networks
Barber, M. J.
Physical Review E, 76(6) (2007) [pdf]
The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.
Module identification in bipartite and directed networks
Guimerà, R.; Sales-Pardo, M. & Amaral, L.
Physical review. E, Statistical, nonlinear, and soft matter physics, 76(3 Pt 2) 036102 (2007) [pdf]
Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of nodes, but links have an origin and an end. We show that directed unipartite networks can be conviniently represented as bipartite networks for module identification purposes. We report a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that enable us to validate the new approach.
Trend Detection in Folksonomies
Hotho, A.; Jäschke, R.; Schmitz, C. & Stumme, G.
Avrithis, Y. S.; Kompatsiaris, Y.; Staab, S. & O'Connor, N. E., ed., 'Proc. First International Conference on Semantics And Digital Media Technology (SAMT) ', 4306(), Lecture Notes in Computer Science, Springer, Heidelberg, 56-70 (2006) [pdf]
As the number of resources on the web exceeds by far the number of documents one can track, it becomes increasingly difficult to remain up to date on ones own areas of interest. The problem becomes more severe with the increasing fraction of multimedia data, from which it is difficult to extract some conceptual description of their contents.
One way to overcome this problem are social bookmark tools, which are rapidly emerging on the web. In such systems, users are setting up lightweight conceptual structures called folksonomies, and overcome thus the knowledge acquisition bottleneck. As more and more people participate in the effort, the use of a common vocabulary becomes more and more stable. We present an approach for discovering topic-specific trends within folksonomies. It is based on a differential adaptation of the PageRank algorithm to the triadic hypergraph structure of a folksonomy. The approach allows for any kind of data, as it does not rely on the internal structure of the documents. In particular, this allows to consider different data types in the same analysis step. We run experiments on a large-scale real-world snapshot of a social bookmarking system.
Wege zur Entdeckung von Communities in Folksonomies
Jäschke, R.; Hotho, A.; Schmitz, C. & Stumme, G.
Braß, S. & Hinneburg, A., ed., 'Proc. 18. Workshop Grundlagen von Datenbanken', Martin-Luther-Universität , Halle-Wittenberg, 80-84 (2006) [pdf]
Ein wichtiger Baustein des neu entdeckten World Wide Web -- des "Web 2.0" -- stellen Folksonomies dar. In diesen Systemen können Benutzer gemeinsam Ressourcen verwalten und
t Schlagwörtern versehen. Die dadurch entstehenden begrifflichen Strukturen stellen ein interessantes Forschungsfeld dar. Dieser Artikel untersucht Ansätze und Wege zur Entdeckung und Strukturierung von Nutzergruppen ("Communities") in Folksonomies.
Online Analysis of Community Evolution in Data Streams.
Aggarwal, C. C. & Yu, P. S.
, 'SDM' (2005) [pdf]
Community detection in complex networks using Extremal Optimization
Duch, J. & Arenas, A.
Physical Review E, 72() 027104 (2005) [pdf]
We propose a novel method to find the community structure in complex networks based on an extremal optimization of the value of modularity. The method outperforms the optimal modularity found by the existing algorithms in the literature. We present the results of the algorithm for computer simulated and real networks and compare them with other approaches. The efficiency and accuracy of the method make it feasible to be used for the accurate identification of community structure in large complex networks.
IT-supported Visualization and Evaluation of Virtual Knowledge Communities. Applying Social Network Intelligence Software in Knowledge Management to enable knowledge oriented People Network Management
Trier, M.
2005 [pdf]
A community-aware search engine
Almeida, R. B. & Almeida, V. A. F.
, 'Proceedings of the 13th international conference on World Wide Web', ACM Press, New York, NY, USA, 413-421 (2004) [pdf]

rrent search technologies work in a "one size fits all" fashion. Therefore, the answer to a query is independent of specific user information need. In this paper we describe a novel ranking technique for personalized search servicesthat combines content-based and community-based evidences. The community-based information is used in order to provide context for queries andis influenced by the current interaction of the user with the service. Ouralgorithm is evaluated using data derived from an actual service available on the Web an online bookstore. We show that the quality of content-based ranking strategies can be improved by the use of communityinformation as another evidential source of relevance. In our experiments the improvements reach up to 48% in terms of average precision.
Defining and identifying communities in networks
Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V. & Parisi, D.
(2004) [pdf]
The investigation of community structures in networks is an important issue
many domains and disciplines. This problem is relevant for social tasks
bjective analysis of relationships on the web), biological inquiries
unctional studies in metabolic, cellular or protein networks) or
chnological problems (optimization of large infrastructures). Several types
algorithm exist for revealing the community structure in networks, but a
neral and quantitative definition of community is still lacking, leading to
intrinsic difficulty in the interpretation of the results of the algorithms
thout any additional non-topological information. In this paper we face this
oblem by introducing two quantitative definitions of community and by showing
w they are implemented in practice in the existing algorithms. In this way
e algorithms for the identification of the community structure become fully
lf-contained. Furthermore, we propose a new local algorithm to detect
mmunities which outperforms the existing algorithms with respect to the
mputational cost, keeping the same level of reliability. The new algorithm is
sted on artificial and real-world graphs. In particular we show the
plication of the new algorithm to a network of scientific collaborations,
ich, for its size, can not be attacked with the usual methods. This new class
local algorithms could open the way to applications to large-scale
chnological and biological applications.
Design and evaluation of a user-based community discovery technique
Almeida, R. & Almeida, V.
'Proceedings of the 4th International Conference on Internet Computing', 17-23(2003) [pdf]
Tractable Group Detection on Large Link Data Sets
Kubica, J.; Moore, A. & Schneider, J.
Wu, X.; Tuzhilin, A. & Shavlik, J., ed., 'The Third IEEE International Conference on Data Mining', IEEE Computer Society, 573-576 (2003)
K-groups: Tractable Group Detection on Large Link Data Sets
Kubica, J. M.; Moore, A. & Schneider, J.
2003, Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA [pdf]
Discovering underlying structure from co-occurrence data is an important task in many fields, including: insurance, intelligence, criminal investigation, epidemiology, human resources, and marketing. For example a store may wish to identify underlying sets of items purchased together or a human resources department may wish to identify groups of employees that collaborate with each other.
Previously Kubica et. al. presented the group detection algorithm (GDA) - an algorithm for finding underlying groupings of entities from co-occurrence data. This algorithm is based on a probabilistic generative model and produces coherent groups that are consistent with prior knowledge. Unfortunately, the optimization used in GDA is slow, making it potentially infeasible for many real world data sets.
To this end, we present k-groups - an algorithm that uses an approach similar to that of k-means (hard clustering and localized updates) to significantly accelerate the discovery of the underlying groups while retaining GDA's probabilistic model. In addition, we show that k-groups is guaranteed to converge to a local minimum. We also compare the performance of GDA and k-groups on several real world and artificial data sets, showing that k-groups' sacrifice in solution quality is significantly offset by its increase in speed. This trade-off makes group detection tractable on significantly larger data sets.
Stochastic Link and Group Detection
Kubica, J.; Moore, A.; Schneider, J. & Yang, Y.
, 'Proceedings of the Eighteenth National Conference on Artificial Intelligence', AAAI Press/MIT Press, 798-804 (2002)
Finding authorities and hubs from link structures on the World Wide Web
Borodin, A.; Roberts, G. O.; Rosenthal, J. S. & Tsaparas, P.
, 'Proceedings of the 10th international conference on World Wide Web', ACM Press, New York, NY, USA, 415-429 (2001) [pdf]
Learning object identification rules for information integration
Tejada, S.; Knoblock, C. A. & Minton, S.
Information Systems, 26(8) 607-633 (2001) [pdf]
When integrating information from multiple websites, the same data objects can exist in inconsistent text formats across sites, making it difficult to identify matching objects using exact text match. We have developed an object identification system called Active Atlas, which compares the objects’ shared attributes in order to identify matching objects. Certain attributes are more important for deciding if a mapping should exist between two objects. Previous methods of object identification have required manual construction of object identification rules or mapping rules for determining the mappings between objects. This manual process is time consuming and error-prone. In our approach. Active Atlas learns to tailor mapping rules, through limited user input, to a specific application domain. The experimental results demonstrate that we achieve higher accuracy and require less user involvement than previous methods across various application domains.