Publications
On the Evolution of Contacts and Communities in Networks of Face-to-Face Proximity
Kibanov, M.; Atzmueller, M.; Scholz, C. & Stumme, G.
, 'Proc. IEEE CPSCom 2013', IEEE Computer Society, Boston, MA, USA (2013)
How Do People Link? Analysis of Contact Structures in Human Face-to-Face Proximity Networks
Scholz, C.; Atzmueller, M.; Kibanov, M. & Stumme, G.
, 'Proc. ASONAM 2013', ACM Press, New York, NY, USA (2013)
Anatomy of a Conference
Macek, B. E.; Scholz, C.; Atzmueller, M. & Stumme, G.
, '23rd ACM Conference on Hypertext and Social Media, HT '12', ACM, Milwaukee, WI, USA, June 25-28, 2012, 245-254 (2012) [pdf]
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.
, 'Proceedings of the 21st ACM conference on Hypertext and hypermedia', Toronto, Canada (2010)
Concept Lattice Orbifolds – First Steps
Borchmann, D. & Ganter, B.
, 22-37 (2009) [pdf]
Concept lattices with symmetries may be simplified by “folding” them along the orbits of their automorphism group. The resulting
agram is often more intuitive than the full lattice diagram, but well defined annotations are required to make the foldeddiagram as informative as the original one. The folding procedure can be extended to formal contexts.
Network analysis of collaboration structure in Wikipedia
Brandes, U.; Kenis, P.; Lerner, J. & van Raaij, D.
, 'WWW '09: Proceedings of the 18th international conference on World wide web', ACM, New York, NY, USA, [http://doi.acm.org/10.1145/1526709.1526808], 731-740 (2009) [pdf]
In this paper we give models and algorithms to describe and analyze the collaboration among authors of Wikipedia from a network analytical perspective. The edit network encodes who interacts how with whom when editing an article; it significantly extends previous network models that code author communities in Wikipedia. Several characteristics summarizing some aspects of the organization process and allowing the analyst to identify certain types of authors can be obtained from the edit network. Moreover, we propose several indicators characterizing the global network structure and methods to visualize edit networks. It is shown that the structural network indicators are correlated with quality labels of the associated Wikipedia articles.
Structure of Heterogeneous Networks
Ghosh, R. & Lerman, K.
(2009) [pdf]
Heterogeneous networks play a key role in the evolution of communities and
e decisions individuals make. These networks link different types of
tities, for example, people and the events they attend. Network analysis
gorithms usually project such networks unto simple graphs composed of
tities of a single type. In the process, they conflate relations between
tities of different types and loose important structural information. We
velop a mathematical framework that can be used to compactly represent and
alyze heterogeneous networks that combine multiple entity and link types. We
neralize Bonacich centrality, which measures connectivity between nodes by
e number of paths between them, to heterogeneous networks and use this
asure to study network structure. Specifically, we extend the popular
dularity-maximization method for community detection to use this centrality
tric. We also rank nodes based on their connectivity to other nodes. One
vantage of this centrality metric is that it has a tunable parameter we can
e to set the length scale of interactions. By studying how rankings change
th this parameter allows us to identify important nodes in the network. We
ply the proposed method to analyze the structure of several heterogeneous
tworks. We show that exploiting additional sources of evidence corresponding
links between, as well as among, different entity types yields new insights
to network structure.
Evaluating Similarity Measures for Emergent Semantics of Social Tagging
Markines, B.; Cattuto, C.; Menczer, F.; Benz, D.; Hotho, A. & Stumme, G.
, '18th International World Wide Web Conference', 641-650 (2009) [pdf]
Social bookmarking systems and their emergent information structures, known as folksonomies, are increasingly important data sources for Semantic Web applications. A key question for harvesting semantics from these systems is how to extend and adapt traditional notions of similarity to folksonomies, and which measures are best suited for applications such as navigation support, semantic search, and ontology learning. Here we build an evaluation framework to compare various general folksonomy-based similarity measures derived from established information-theoretic, statistical, and practical measures. Our framework deals generally and symmetrically with users, tags, and resources. For evaluation purposes we focus on similarity among tags and resources, considering different ways to aggregate annotations across users. After comparing how tag similarity measures predict user-created tag relations, we provide an external grounding by user-validated semantic proxies based on WordNet and the Open Directory. We also investigate the issue of scalability. We ?nd that mutual information with distributional micro-aggregation across users yields the highest accuracy, but is not scalable; per-user projection with collaborative aggregation provides the best scalable approach via incremental computations. The results are consistent across resource and tag similarity.
De-anonymizing Social Networks
Narayanan, A. & Shmatikov, V.
(2009) [pdf]
Operators of online social networks are increasingly sharing potentially
nsitive information about users and their relationships with advertisers,
plication developers, and data-mining researchers. Privacy is typically
otected by anonymization, i.e., removing names, addresses, etc.
We present a framework for analyzing privacy and anonymity in social networks
d develop a new re-identification algorithm targeting anonymized
cial-network graphs. To demonstrate its effectiveness on real-world networks,
show that a third of the users who can be verified to have accounts on both
itter, a popular microblogging service, and Flickr, an online photo-sharing
te, can be re-identified in the anonymous Twitter graph with only a 12% error
te.
Our de-anonymization algorithm is based purely on the network topology, does
t require creation of a large number of dummy "sybil" nodes, is robust to
ise and all existing defenses, and works even when the overlap between the
rget network and the adversary's auxiliary information is small.
Efficient sampling of information in social networks
Das, G.; Koudas, N.; Papagelis, M. & Puttaswamy, S.
, 'SSM '08: Proceeding of the 2008 ACM workshop on Search in social media', ACM, New York, NY, USA, [http://doi.acm.org/10.1145/1458583.1458594], 67-74 (2008) [pdf]
As online social networking emerges, there has been increased interest to utilize the underlying social structure as well as the available social information to improve search. In this paper, we focus on improving the performance of information collection from the neighborhood of a user in a dynamic social network. To this end, we introduce sampling based algorithms to quickly approximate quantities of interest from the vicinity of a user's social graph. We then introduce and analyze variants of this basic scheme exploring correlations across our samples. Models of centralized and distributed social networks are considered. We show that our algorithms can be utilized to rank items in the neighborhood of a user, assuming that information for each user in the network is available. Using real and synthetic data sets, we validate the results of our analysis and demonstrate the efficiency of our algorithms in approximating quantities of interest. The methods we describe are general and can probably be easily adopted in a variety of strategies aiming to efficiently collect information from a social graph.
Planetary-scale views on a large instant-messaging network
Leskovec, J. & Horvitz, E.
, 'WWW '08: Proceeding of the 17th international conference on World Wide Web', ACM, New York, NY, USA, [http://doi.acm.org/10.1145/1367497.1367620], 915-924 (2008) [pdf]
We present a study of anonymized data capturing a month of high-level communication activities within the whole of the Microsoft Messenger instant-messaging system. We examine characteristics and patterns that emerge from the collective dynamics of large numbers of people, rather than the actions and characteristics of individuals. The dataset contains summary properties of 30 billion conversations among 240 million people. From the data, we construct a communication graph with 180 million nodes and 1.3 billion undirected edges, creating the largest social network constructed and analyzed to date. We report on multiple aspects of the dataset and synthesized graph. We find that the graph is well-connected and robust to node removal. We investigate on a planetary-scale the oft-cited report that people are separated by "six degrees of separation" and find that the average path length among Messenger users is 6.6. We find that people tend to communicate more with each other when they have similar age, language, and location, and that cross-gender conversations are both more frequent and of longer duration than conversations with the same gender.
Graph OLAP: Towards Online Analytical Processing on Graphs
Zhu, F.; Chen, C.; Yan, X.; Han, J. & Yu, P. S.
, 'Proc. 2008 Int. Conf. on Data Mining (ICDM'08), Pisa, Italy, Dec. 2008.' (2008)
Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography
Backstrom, L.; Dwork, C. & Kleinberg, J.
, 'Proceedings of the 16th international conference on World Wide Web', WWW '07, ACM, New York, NY, USA, [10.1145/1242572.1242598], 181-190 (2007) [pdf]
In a social network, nodes correspond topeople or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.
Combating spam in tagging systems
Koutrika, G.; Effendi, F. A.; Gyöngyi, Z.; Heymann, P. & Garcia-Molina, H.
, 'AIRWeb '07: Proc. of the 3rd int. workshop on Adversarial inf. retrieval on the web', 57-64 (2007)
Network Properties of Folksonomies
Schmitz, C.; Grahl, M.; Hotho, A.; Stumme, G.; Catutto, C.; Baldassarri, A.; Loreto, V. & Servedio, V. D. P.
, 'Proc. WWW2007 Workshop ``Tagging and Metadata for Social Information Organization''', Banff (2007) [pdf]
Testing multitheoretical, multilevel hypotheses about organizational networks: An analytic framework and empirical example
Faust, K.; Wassermann & Contractor, N.
, 31(), 681-703 (2006) [pdf]
Semantic Network Analysis of Ontologies
Hoser, B.; Hotho, A.; Jäschke, R.; Schmitz, C. & Stumme, G.
Sure, Y. & Domingue, J., ed., 'The Semantic Web: Research and Applications', 4011(), LNAI, Springer, Heidelberg, 514-529 (2006) [pdf]
A key argument for modeling knowledge in ontologies is the easy
-use and re-engineering of the knowledge. However, beside
nsistency checking, current ontology engineering tools provide
ly basic functionalities for analyzing ontologies. Since
tologies can be considered as (labeled, directed) graphs, graph
alysis techniques are a suitable answer for this need. Graph
alysis has been performed by sociologists for over 60 years, and
sulted in the vivid research area of Social Network Analysis
NA). While social network structures in general currently receive
gh attention in the Semantic Web community, there are only very
w SNA applications up to now, and virtually none for analyzing the
ructure of ontologies.

e illustrate in this paper the benefits of applying SNA to
tologies and the Semantic Web, and discuss which research topics
ise on the edge between the two areas. In particular, we discuss
w different notions of centrality describe the core content and
ructure of an ontology. From the rather simple notion of degree
ntrality over betweenness centrality to the more complex
genvector centrality based on Hermitian matrices, we illustrate
e insights these measures provide on two ontologies, which are
fferent in purpose, scope, and size.

tagging, communities, vocabulary, evolution
Sen, S.; Lam, S. K.; Rashid, A. M.; Cosley, D.; Frankowski, D.; Osterhouse, J.; Harper, M. F. & Riedl, J.
, 'CSCW '06: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work', ACM Press, New York, NY, USA, [10.1145/1180875.1180904], 181-190 (2006) [pdf]
Proceedings of the First Workshop on Semantic Network Analysis
2005, Stumme, G.; Hoser, B.; Schmitz, C. & Alani, H., ed., CEUR Proceedings, Aachen [pdf]
Visualization of bibliographic networks with a reshaped landscape metaphor
Brandes, U. & Willhalm, T.
, 'Proceedings of the symposium on Data Visualisation 2002', VISSYM '02, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 159-ff (2002) [pdf]
We describe a novel approach to visualize bibliographic networks that facilitates the simultaneous identification of clusters (e.g., topic areas) and prominent entities (e.g., surveys or landmark papers). While employing the landscape metaphor proposed in several earlier works, we introduce new means to determine relevant parameters of the landscape. Moreover, we are able to compute prominent entities, clustering of entities, and the landscape's surface in a surprisingly simple and uniform way. The effectiveness of our network visualizations is illustrated on data from the graph drawing literature.