part of the Web 2.0. In such systems
users describe bookmarks by keywords
called tags. The structure behind these social
systems, called folksonomies, can be viewed
as a tripartite hypergraph of user, tag and resource
nodes. This underlying network shows
specific structural properties that explain its
growth and the possibility of serendipitous
exploration.
Today’s search engines represent the gateway
to retrieve information from the World Wide
Web. Short queries typically consisting of
two to three words describe a user’s information
need. In response to the displayed
results of the search engine, users click on
the links of the result page as they expect
the answer to be of relevance.
This clickdata can be represented as a folksonomy
in which queries are descriptions of
clicked URLs. The resulting network structure,
which we will term logsonomy is very
similar to the one of folksonomies. In order
to find out about its properties, we analyze
the topological characteristics of the tripartite
hypergraph of queries, users and bookmarks
on a large snapshot of del.icio.us and
on query logs of two large search engines.
All of the three datasets show small world
properties. The tagging behavior of users,
which is explained by preferential attachment
of the tags in social bookmark systems, is
reflected in the distribution of single query
words in search engines. We can conclude
that the clicking behaviour of search engine
users based on the displayed search results
and the tagging behaviour of social bookmarking
users is driven by similar dynamics. ER - TY - JOUR AU - Leskovec, J. AU - Horvitz, E. T1 - Planetary-scale views on a large instant-messaging network JO - PY - 2008/ VL - IS - SP - EP - UR - http://scholar.google.de/scholar.bib?q=info:dvYmn_qj6NQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - analysis KW - instant KW - messenger KW - network KW - small KW - ur KW - world L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Almendral, Juan A. AU - Oliveira, J.G. AU - López, L. AU - Mendes, J.F.F. AU - Sanjuán, Miguel A.F. T1 - The network of scientific collaborations within the European framework programme JO - Physica A: Statistical Mechanics and its Applications PY - 2007/ VL - 384 IS - 2 SP - 675 EP - 683 UR - http://www.sciencedirect.com/science/article/B6TVG-4NTJH10-4/2/b209f12299c9e1d367a8298e7d986215 M3 - DOI: 10.1016/j.physa.2007.05.049 KW - analysis KW - network KW - social KW - toread KW - ur L1 - SN - N1 - N1 - AB - We use the emergent field of complex networks to analyze the network of scientific collaborations between entities (universities, research organizations, industry related companies,...) which collaborate in the context of the so-called framework programme. We demonstrate here that it is a scale-free network with an accelerated growth, which implies that the creation of new collaborations is encouraged. Moreover, these collaborations possess hierarchical modularity. Likewise, we find that the information flow depends on the size of the participants but not on geographical constraints. ER - TY - GEN AU - Brandes, U. AU - Delling, D. AU - Gaertler, M. AU - Goerke, R. AU - Hoefer, M. AU - Nikoloski, Z. AU - Wagner, D. A2 - T1 - Maximizing Modularity is hard JO - PB - AD - PY - 2006/ VL - IS - SP - EP - UR - http://arxiv.org/abs/physics/0608255 M3 - KW - community KW - complexity KW - detection KW - modularity KW - network KW - npc L1 - N1 - N1 - AB - Several algorithms have been proposed to compute partitions of networks
into communities that score high on a graph clustering index called
modularity. While publications on these algorithms typically contain
experimental evaluations to emphasize the plausibility of results,
none of these algorithms has been shown to actually compute optimal
partitions. We here settle the unknown complexity status of modularity
maximization by showing that the corresponding decision version is
NP-complete in the strong sense. As a consequence, any efficient,
i.e. polynomial-time, algorithm is only heuristic and yields suboptimal
partitions on many instances. ER - TY - CONF AU - Hoser, Bettina AU - Hotho, Andreas AU - Jäschke, Robert AU - Schmitz, Christoph AU - Stumme, Gerd A2 - T1 - Semantic Network Analysis of Ontologies T2 - The Semantic Web: Research and Applications PB - Springer CY - PY - 2006/06 M2 - VL - IS - SP - EP - UR - M3 - KW - analysis KW - network KW - ontology KW - semantic L1 - SN - N1 - N1 - AB - A key argument for modeling knowledge in ontologies is the easy re-use and re-engineering of the knowledge. However, current ontology engineering tools provide only basic functionalities for analyzing ontologies. Since ontologies can be considered as graphs, graph analysis techniques are a suitable answer for this need. Graph analysis has been performed by sociologists for over 60 years, and resulted in the vivid research area of Social Network Analysis (SNA). While social network structures currently receive high attention in the Semantic Web community, there are only very
few SNA applications, and virtually none for analyzing the
structure of ontologies.
We illustrate the benefits of applying SNA to ontologies and the Semantic Web, and discuss which research topics arise on the edge between the two areas. In particular, we discuss how different notions of centrality describe the core content and structure of an ontology. From the rather simple notion of degree centrality over betweenness centrality to the more complex eigenvector centrality, we illustrate the insights these measures provide on two ontologies, which are different in purpose, scope, and size. ER - TY - CONF AU - Kumar, Ravi AU - Novak, Jasmine AU - Tomkins, Andrew A2 - T1 - Structure and evolution of online social networks T2 - KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining PB - ACM CY - New York, NY, USA PY - 2006/ M2 - VL - IS - SP - 611 EP - 617 UR - http://portal.acm.org/citation.cfm?id=1150402.1150476 M3 - http://doi.acm.org/10.1145/1150402.1150476 KW - analysis KW - link KW - network KW - sna KW - structure KW - toread KW - ur KW - user L1 - SN - 1-59593-339-5 N1 - N1 - AB - In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.We present a simple model of network growth which captures these aspects of component structure. The model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network. ER - TY - JOUR AU - Li, L. AU - Alderson, D. AU - Doyle, J.C. AU - Willinger, W. T1 - Towards a theory of scale-free graphs: Definition, properties, and implications JO - Internet Mathematics PY - 2005/ VL - 2 IS - 4 SP - 431 EP - 523 UR - http://scholar.google.de/scholar.bib?q=info:Xi5NYPJyMvMJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - free KW - law KW - network KW - power KW - scale KW - theory KW - ur L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Menczer, F. T1 - Lexical and semantic clustering by web links JO - Journal of the American Society for Information Science and Technology PY - 2004/ VL - 55 IS - 14 SP - 1261 EP - 1269 UR - http://scholar.google.de/scholar.bib?q=info:qmPuziT0_h0J:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - link KW - locality KW - network KW - structure KW - topical KW - toread KW - ur L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, M. E. J. T1 - The structure and function of complex networks JO - SIAM Review PY - 2003/ VL - 45 IS - 2 SP - 167 EP - 256 UR - M3 - KW - graph KW - introduction KW - network KW - review KW - survey KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, M. E. J. AU - Park, Juyong T1 - Why Social Networks Are Different from Other Types of Networks JO - Phys. Rev. E PY - 2003/10 VL - 68 IS - 3 SP - EP - UR - M3 - KW - analysis KW - network KW - sna L1 - SN - N1 - N1 - AB - We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have nontrivial clustering or network transitivity and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could account for the observed clustering. We demonstrate that group structure in networks can also account for degree correlations. We show using a simple model that we should expect assortative mixing in such networks whenever there is variation in the sizes of the groups and that the predicted level of assortative mixing compares well with that observed in real-world networks. ER - TY - JOUR AU - Girvan, M. AU - Newman, M. E. J. T1 - Community structure in social and biological networks JO - PNAS PY - 2002/06 VL - 99 IS - 12 SP - 7821 EP - 7826 UR - M3 - KW - community KW - detection KW - modularity KW - network L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, M. E. J. AU - Forrest, Stephanie AU - Balthrop, Justin T1 - Email networks and the spread of computer viruses JO - Phys. Rev. E PY - 2002/10 VL - 66 IS - 3 SP - EP - UR - M3 - 10.1103/PhysRevE.66.035101 KW - degree KW - network KW - social L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Vázquez, A. AU - Pastor-Satorras, R. AU - Vespignani, A. T1 - Large-scale topological and dynamical properties of the Internet JO - Physical Review E PY - 2002/ VL - 65 IS - 6 SP - EP - UR - http://scholar.google.de/scholar.bib?q=info:sEuhI6oKjFoJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - analysis KW - correlation KW - degree KW - function KW - link KW - network L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Pastor-Satorras, R. AU - Vázquez, A. AU - Vespignani, A. T1 - Dynamical and correlation properties of the Internet JO - Physical Review Letters PY - 2001/ VL - 87 IS - 25 SP - EP - UR - http://scholar.google.de/scholar.bib?q=info:KLiz1q2axUQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - analysis KW - correlation KW - degree KW - network L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Amaral, L. A. N. AU - Scala, A. AU - Barthélémy, M. AU - Stanley, H. E. T1 - Classes of small-world networks JO - PNAS PY - 2000/ VL - 97 IS - 21 SP - EP - UR - M3 - KW - network KW - properties KW - statistics L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Broder, A. AU - Kumar, R. AU - Maghoul, F. AU - Raghavan, P. AU - Rajagopalan, S. AU - Stata, R. AU - Tomkins, A. AU - Wiener, J. T1 - Graph structure in the web JO - Computer Networks PY - 2000/ VL - 33 IS - 1-6 SP - 309 EP - 320 UR - http://scholar.google.de/scholar.bib?q=info:XK3rB5QCtqgJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0 M3 - KW - analysis KW - network KW - scc KW - structure KW - toread KW - ur KW - web L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Barabasi, A. L. AU - Albert, R. T1 - Emergence of scaling in random networks JO - Science PY - 1999/october VL - 286 IS - 5439 SP - 509 EP - 512 UR - http://view.ncbi.nlm.nih.gov/pubmed/10521342 M3 - KW - graph KW - network KW - properties KW - statistics L1 - SN - N1 - N1 - AB - Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems. ER - TY - JOUR AU - Erdős, Pal AU - Rényi, Alfréd T1 - On Random Graphs JO - Publications Mathematicae PY - 1959/ VL - 6 IS - SP - EP - UR - M3 - KW - analysis KW - graphs KW - network KW - random L1 - SN - N1 - N1 - AB - ER -