@inproceedings{schneider2009understanding, abstract = {Online Social Networks (OSNs) have already attracted more than half a billion users. However, our understanding of which OSN features attract and keep the attention of these users is poor. Studies thus far have relied on surveys or interviews of OSN users or focused on static properties, e. g., the friendship graph, gathered via sampled crawls. In this paper, we study how users actually interact with OSNs by extracting clickstreams from passively monitored network traffic. Our characterization of user interactions within the OSN for four different OSNs (Facebook, LinkedIn, Hi5, and StudiVZ) focuses on feature popularity, session characteristics, and the dynamics within OSN sessions. We find, for example, that users commonly spend more than half an hour interacting with the OSNs while the byte contributions per OSN session are relatively small.}, acmid = {1644899}, address = {New York, NY, USA}, author = {Schneider, Fabian and Feldmann, Anja and Krishnamurthy, Balachander and Willinger, Walter}, booktitle = {Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference}, doi = {10.1145/1644893.1644899}, interhash = {69b16bc81a34c976ea724b5e82ba2d8e}, intrahash = {f7ef42a9ba8edf63b6079a053d6bb9c6}, isbn = {978-1-60558-771-4}, location = {Chicago, Illinois, USA}, numpages = {14}, pages = {35--48}, publisher = {ACM}, series = {IMC '09}, title = {Understanding Online Social Network Usage from a Network Perspective}, url = {http://doi.acm.org/10.1145/1644893.1644899}, year = 2009 } @inproceedings{benevenuto2009characterizing, abstract = {Understanding how users behave when they connect to social networking sites creates opportunities for better interface design, richer studies of social interactions, and improved design of content distribution systems. In this paper, we present a first of a kind analysis of user workloads in online social networks. Our study is based on detailed clickstream data, collected over a 12-day period, summarizing HTTP sessions of 37,024 users who accessed four popular social networks: Orkut, MySpace, Hi5, and LinkedIn. The data were collected from a social network aggregator website in Brazil, which enables users to connect to multiple social networks with a single authentication. Our analysis of the clickstream data reveals key features of the social network workloads, such as how frequently people connect to social networks and for how long, as well as the types and sequences of activities that users conduct on these sites. Additionally, we crawled the social network topology of Orkut, so that we could analyze user interaction data in light of the social graph. Our data analysis suggests insights into how users interact with friends in Orkut, such as how frequently users visit their friends' or non-immediate friends' pages. In summary, our analysis demonstrates the power of using clickstream data in identifying patterns in social network workloads and social interactions. Our analysis shows that browsing, which cannot be inferred from crawling publicly available data, accounts for 92% of all user activities. Consequently, compared to using only crawled data, considering silent interactions like browsing friends' pages increases the measured level of interaction among users.}, acmid = {1644900}, address = {New York, NY, USA}, author = {Benevenuto, Fabr\'{\i}cio and Rodrigues, Tiago and Cha, Meeyoung and Almeida, Virg\'{\i}lio}, booktitle = {Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference}, doi = {10.1145/1644893.1644900}, interhash = {ed9b10d4f36f90ddde9b95ce45b0b0be}, intrahash = {e5e25244e1ca2316a7871727e2df2bb9}, isbn = {978-1-60558-771-4}, location = {Chicago, Illinois, USA}, numpages = {14}, pages = {49--62}, publisher = {ACM}, series = {IMC '09}, title = {Characterizing User Behavior in Online Social Networks}, url = {http://doi.acm.org/10.1145/1644893.1644900}, year = 2009 } @article{jiang2013understanding, abstract = {Popular online social networks (OSNs) like Facebook and Twitter are changing the way users communicate and interact with the Internet. A deep understanding of user interactions in OSNs can provide important insights into questions of human social behavior and into the design of social platforms and applications. However, recent studies have shown that a majority of user interactions on OSNs are latent interactions, that is, passive actions, such as profile browsing, that cannot be observed by traditional measurement techniques. In this article, we seek a deeper understanding of both active and latent user interactions in OSNs. For quantifiable data on latent user interactions, we perform a detailed measurement study on Renren, the largest OSN in China with more than 220 million users to date. All friendship links in Renren are public, allowing us to exhaustively crawl a connected graph component of 42 million users and 1.66 billion social links in 2009. Renren also keeps detailed, publicly viewable visitor logs for each user profile. We capture detailed histories of profile visits over a period of 90 days for users in the Peking University Renren network and use statistics of profile visits to study issues of user profile popularity, reciprocity of profile visits, and the impact of content updates on user popularity. We find that latent interactions are much more prevalent and frequent than active events, are nonreciprocal in nature, and that profile popularity is correlated with page views of content rather than with quantity of content updates. Finally, we construct latent interaction graphs as models of user browsing behavior and compare their structural properties, evolution, community structure, and mixing times against those of both active interaction graphs and social graphs.}, acmid = {2517040}, address = {New York, NY, USA}, articleno = {18}, author = {Jiang, Jing and Wilson, Christo and Wang, Xiao and Sha, Wenpeng and Huang, Peng and Dai, Yafei and Zhao, Ben Y.}, doi = {10.1145/2517040}, interhash = {af18171c38a0b07fce62fb3fac5c6322}, intrahash = {aa9695f56135fd58de32b5b4a4c73698}, issn = {1559-1131}, issue_date = {October 2013}, journal = {ACM Trans. Web}, month = nov, number = 4, numpages = {39}, pages = {18:1--18:39}, publisher = {ACM}, title = {Understanding Latent Interactions in Online Social Networks}, url = {http://doi.acm.org/10.1145/2517040}, volume = 7, year = 2013 } @misc{batagelj2003algorithm, abstract = {The structure of large networks can be revealed by partitioning them to smaller parts, which are easier to handle. One of such decompositions is based on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$, $m$ is the number of lines, algorithm for determining the cores decomposition of a given network is presented.}, author = {Batagelj, V. and Zaversnik, M.}, interhash = {63be428635128d4eebd095e2ca44cdf2}, intrahash = {d533733cd010732a5ca81417f4deca0a}, note = {cite arxiv:cs/0310049}, title = {An O(m) Algorithm for Cores Decomposition of Networks}, url = {http://arxiv.org/abs/cs/0310049}, year = 2003 } @article{seidman1983network, abstract = {Social network researchers have long sought measures of network cohesion, Density has often been used for this purpose, despite its generally admitted deficiencies. An approach to network cohesion is proposed that is based on minimum degree and which produces a sequence of subgraphs of gradually increasing cohesion. The approach also associates with any network measures of local density which promise to be useful both in characterizing network structures and in comparing networks.}, author = {Seidman, Stephen B.}, doi = {10.1016/0378-8733(83)90028-X}, interhash = {bdba8b78574faec3a7315423e29b7556}, intrahash = {402ff073bdbfef97765e307068f59110}, issn = {0378-8733}, journal = {Social Networks}, number = 3, pages = {269 - 287}, title = {Network structure and minimum degree}, url = {http://www.sciencedirect.com/science/article/pii/037887338390028X}, volume = 5, year = 1983 } @article{Ross2009578, abstract = {Facebook is quickly becoming one of the most popular tools for social communication. However, Facebook is somewhat different from other Social Networking Sites as it demonstrates an offline-to-online trend; that is, the majority of Facebook Friends are met offline and then added later. The present research investigated how the Five-Factor Model of personality relates to Facebook use. Despite some expected trends regarding Extraversion and Openness to Experience, results indicated that personality factors were not as influential as previous literature would suggest. The results also indicated that a motivation to communicate was influential in terms of Facebook use. It is suggested that different motivations may be influential in the decision to use tools such as Facebook, especially when individual functions of Facebook are being considered.}, author = {Ross, Craig and Orr, Emily S. and Sisic, Mia and Arseneault, Jaime M. and Simmering, Mary G. and Orr, R. Robert}, doi = {10.1016/j.chb.2008.12.024}, interhash = {98f45e3865f7e4802258347ee91e678b}, intrahash = {fbcbb77a298da03d1e2d8bcd9ac3e0b4}, issn = {0747-5632}, journal = {Computers in Human Behavior}, note = {Including the Special Issue: State of the Art Research into Cognitive Load Theory}, number = 2, pages = {578 - 586}, title = {Personality and motivations associated with Facebook use}, url = {http://www.sciencedirect.com/science/article/pii/S0747563208002355}, volume = 25, year = 2009 } @incollection{koschtzki2005centrality, abstract = {Centrality indices are to quantify an intuitive feeling that in most networks some vertices or edges are more central than others. Many vertex centrality indices were introduced for the first time in the 1950s: e.g., the Bavelas index [50, 51], degree centrality [483] or a first feedback centrality, introduced by Seeley [510]. These early centralities raised a rush of research in which manifold applications were found. However, not every centrality index was suitable to every application, so with time, dozens of new centrality indices were published. This chapter will present some of the more influential, ‘classic’ centrality indices. We do not strive for completeness, but hope to give a catalog of basic centrality indices with some of their main applications.}, address = {Berlin / Heidelberg}, affiliation = {IPK Gatersleben, Corrensstraße 3, 06466 Gatersleben, Germany}, author = {Koschützki, Dirk and Lehmann, Katharina and Peeters, Leon and Richter, Stefan and Tenfelde-Podehl, Dagmar and Zlotowski, Oliver}, booktitle = {Network Analysis}, doi = {10.1007/978-3-540-31955-9_3}, editor = {Brandes, Ulrik and Erlebach, Thomas}, interhash = {8bfa60518049d9dbc7f6ce7b5c2914be}, intrahash = {567d2f61b08e78af53463b2a30729830}, isbn = {978-3-540-24979-5}, keyword = {Computer Science}, pages = {16-61}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Centrality Indices}, url = {http://dx.doi.org/10.1007/978-3-540-31955-9_3}, volume = 3418, year = 2005 } @book{brandes2005network, address = {[New York]}, author = {Brandes, Ulrik. and Erlebach, Thomas.}, interhash = {ae40403faa9a80926c66da73cf6e29ba}, intrahash = {11695c81746f2ac6e25fab7c6ed49fbf}, isbn = {9783540249795 3540249796 9783540319559 3540319557}, publisher = {Springer-Verlag Berlin/Heidelberg}, refid = {318289062}, title = {Network Analysis}, url = {http://www.worldcat.org/search?qt=worldcat_org_all&q=3540249796}, year = 2005 } @misc{Ren2011, abstract = { It has been known for a long time that citation networks are always highly clustered, such as the existences of abundant triangles and high clustering coefficient. In a growth model, one typical way to produce clustering is using the trid formation mechanism. However, we find that this mechanism fails to generate enough triangles in a real-world citation network. By analyzing the network, it is found that one paper always cites papers that are already highly connected. We point out that the highly connected papers may refer to similar research topic and one subsequent paper tends to cite all of them. Based on this assumption, we propose a growth model for citation networks in which a new paper i firstly attaches to one relevant paper j and then with a probability links those papers in the same clique to which j belongs. We compare our model to two real-world citation networks - one on a special research area and the other on multidisciplinary sciences. Results show that for the two networks the in-degree distributions are matched and the clustering features, i.e., the number of triangles and the average clustering coefficient, are well reproduced. }, author = {Ren, Fu-Xin and Cheng, Xue-Qi and Shen, Hua-Wei}, interhash = {2aab1505ce7da27402449873fb57b48e}, intrahash = {d668e639ed78f4c7ec53eeba64d8ae2a}, note = {cite arxiv:1104.4209}, title = {Modeling the clustering in citation networks}, url = {http://arxiv.org/abs/1104.4209}, year = 2011 } @incollection{lerner2005assignments, abstract = {9.0. 9.0.1. Preliminaries 9.0.2. Role Graph 9.1. Structural Equivalence 9.1.1. Lattice of Equivalence Relations 9.1.2. Lattice of Structural Equivalences 9.1.3. Computation of Structural Equivalences 9.2. Regular Equivalence 9.2.1. Elementary Properties 9.2.2. Lattice Structure and Regular Interior 9.2.3. Computation of Regular Interior 9.2.4. The Role Assignment Problem 9.2.5. Existence of k-Role Assignments 9.3. Other Equivalences 9.3.1. Exact Role Assignments 9.3.2. Automorphic and Orbit Equivalence 9.3.3. Perfect Equivalence 9.3.4. Relative Regular Equivalence 9.4. Graphs with Multiple Relations 9.5. The Semigroup of a Graph 9.5.1. Winship-Pattison Role Equivalence 9.6. Chapter Notes}, address = {Berlin / Heidelberg}, affiliation = {Computer & Information Science, University of Konstanz, Box D 67, 78457 Konstanz Germany}, author = {Lerner, Jürgen}, booktitle = {Network Analysis}, doi = {10.1007/978-3-540-31955-9_9}, editor = {Brandes, Ulrik and Erlebach, Thomas}, interhash = {59200f990b15e99c7ab3df74fcb8443e}, intrahash = {7385d25825c7692ffdc9b12b0ed85989}, pages = {216-252}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Role Assignments}, url = {http://dx.doi.org/10.1007/978-3-540-31955-9_9}, volume = 3418, year = 2005 } @inproceedings{scripps2007roles, abstract = {A node role is a subjective characterization of the part it plays in a network structure. Knowing the role of a node is important for many link mining applications. For example, in Web search, nodes that are deemed to be authorities on a given topic are often found to be most relevant to the user's queries. There are a number of metrics that can be used to assign roles to individual nodes in a network, including degree, closeness, and betweenness. None of these metrics, however, take into account the community structure that underlies the network. In this paper we define community-based roles that the nodes can assume (ambassadors, big fish, loners, and bridges) and show how existing link mining techniques can be improved by knowledge of such roles. A new community-based metric is introduced for estimating the number of communities linked to a node. Using this metric and a modification of degree, we show how to assign community-based roles to the nodes. We also illustrate the benefits of knowing the community-based node roles in the context of link-based classification and influence maximization.}, acmid = {1348553}, address = {New York, NY, USA}, author = {Scripps, Jerry and Tan, Pang-Ning and Esfahanian, Abdol-Hossein}, booktitle = {Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis}, doi = {http://doi.acm.org/10.1145/1348549.1348553}, interhash = {bc67321ee8dc1e7db1c3c234833a5519}, intrahash = {4435192c25bfc86b47f030011f4ce1ef}, isbn = {978-1-59593-848-0}, location = {San Jose, California}, numpages = {10}, pages = {26--35}, publisher = {ACM}, series = {WebKDD/SNA-KDD '07}, title = {Node roles and community structure in networks}, url = {http://doi.acm.org/10.1145/1348549.1348553}, year = 2007 } @article{springerlink:10.1007/s11238-008-9109-z, abstract = {In this paper, we study a model of influence in a social network. It is assumed that each player has an inclination to say YES or NO which, due to influence of other players, may be different from the decision of the player. The point of departure here is the concept of the Hoede–Bakker index—the notion which computes the overall decisional ‘power’ of a player in a social network. The main drawback of the Hoede–Bakker index is that it hides the actual role of the influence function, analyzing only the final decision in terms of success and failure. In this paper, we separate the influence part from the group decision part, and focus on the description and analysis of the influence part. We propose among other descriptive tools a definition of a (weighted) influence index of a coalition upon an individual. Moreover, we consider different influence functions representative of commonly encountered situations. Finally, we propose a suitable definition of a modified decisional power.}, affiliation = {Université Paris I Panthéon-Sorbonne Centre d’Economie de la Sorbonne 106-112 Bd de l’Hôpital 75013 Paris France}, author = {Grabisch, Michel and Rusinowska, Agnieszka}, doi = {10.1007/s11238-008-9109-z}, interhash = {e905db2be4b4d2e792719e9b8f445951}, intrahash = {37444465dc4376fd111296cc8c9ba1de}, issn = {0040-5833}, issue = {1}, journal = {Theory and Decision}, keyword = {Business and Economics}, pages = {69-96}, publisher = {Springer Netherlands}, title = {A model of influence in a social network}, url = {http://dx.doi.org/10.1007/s11238-008-9109-z}, volume = 69, year = 2010 } @article{journals/corr/abs-1006-1260, author = {Isella, Lorenzo and Stehlé, Juliette and Barrat, Alain and Cattuto, Ciro and Pinton, Jean-François and den Broeck, Wouter Van}, ee = {http://arxiv.org/abs/1006.1260}, interhash = {4a20da6d41e4c1e86e8c04c47b22237c}, intrahash = {53c0555c19fbfd6af5952e2a3abcbdd2}, journal = {CoRR}, note = {informal publication}, title = {What's in a crowd? Analysis of face-to-face behavioral networks}, url = {http://dblp.uni-trier.de/db/journals/corr/corr1006.html#abs-1006-1260}, volume = {abs/1006.1260}, year = 2010 } @book{nooy2005exploratory, asin = {0521602629}, author = {de Nooy, Wouter and Mrvar, Andrej and Batagelj, Vladimir}, dewey = {300.285}, ean = {9780521602624}, edition = {illustrated edition}, interhash = {f482ff433e1826b278a27c5a7474f37e}, intrahash = {fa414ff6ed7eb359bf598ac46fc38154}, isbn = {0521602629}, publisher = {Cambridge University Press}, title = {Exploratory Social Network Analysis with Pajek (Structural Analysis in the Social Sciences)}, url = {http://www.amazon.com/Exploratory-Network-Analysis-Structural-Sciences/dp/0521602629}, year = 2005 } @misc{Ghosh2009, abstract = { Heterogeneous networks play a key role in the evolution of communities and the decisions individuals make. These networks link different types of entities, for example, people and the events they attend. Network analysis algorithms usually project such networks unto simple graphs composed of entities of a single type. In the process, they conflate relations between entities of different types and loose important structural information. We develop a mathematical framework that can be used to compactly represent and analyze heterogeneous networks that combine multiple entity and link types. We generalize Bonacich centrality, which measures connectivity between nodes by the number of paths between them, to heterogeneous networks and use this measure to study network structure. Specifically, we extend the popular modularity-maximization method for community detection to use this centrality metric. We also rank nodes based on their connectivity to other nodes. One advantage of this centrality metric is that it has a tunable parameter we can use to set the length scale of interactions. By studying how rankings change with this parameter allows us to identify important nodes in the network. We apply the proposed method to analyze the structure of several heterogeneous networks. We show that exploiting additional sources of evidence corresponding to links between, as well as among, different entity types yields new insights into network structure. }, author = {Ghosh, Rumi and Lerman, Kristina}, interhash = {761e199eb96643cf601e15cb03c3285a}, intrahash = {3a4a889123d20e0a4d14d06f670de54b}, note = {cite arxiv:0906.2212 }, title = {Structure of Heterogeneous Networks}, url = {http://arxiv.org/abs/0906.2212}, year = 2009 } @misc{Lambiotte2005, abstract = { We describe online collaborative communities by tripartite networks, the nodes being persons, items and tags. We introduce projection methods in order to uncover the structures of the networks, i.e. communities of users, genre families... To do so, we focus on the correlations between the nodes, depending on their profiles, and use percolation techniques that consist in removing less correlated links and observing the shaping of disconnected islands. The structuring of the network is visualised by using a tree representation. The notion of diversity in the system is also discussed. }, author = {Lambiotte, R. and Ausloos, M.}, interhash = {7a9dab1c733e8e1982d5f91979749ce9}, intrahash = {65c6f348a54f872fb3e60b4bd64b485b}, note = {cite arxiv:cs.DS/0512090 }, title = {Collaborative tagging as a tripartite network}, url = {http://arxiv.org/abs/cs/0512090}, year = 2005 } @inproceedings{hotho2006emergent, abstract = {Social bookmark tools are rapidly emerging on the Web. In such systems users are setting up lightweight conceptual structures called folksonomies. The reason for their immediate success is the fact that no specific skills are needed for participating. In this paper we specify a formal model for folksonomies, briefly describe our own system BibSonomy, which allows for sharing both bookmarks and publication references, and discuss first steps towards emergent semantics.}, address = {Bonn}, author = {Hotho, Andreas and Jäschke, Robert and Schmitz, Christoph and Stumme, Gerd}, booktitle = {Informatik 2006 -- Informatik für Menschen. Band 2}, editor = {Hochberger, Christian and Liskowsky, Rüdiger}, interhash = {53e5677ab0bf1a8f5a635cc32c9082ba}, intrahash = {05043cc20f1e0f5a612135c970e4f1ac}, month = oct, note = {Proc. Workshop on Applications of Semantic Technologies, Informatik 2006}, publisher = {Gesellschaft für Informatik}, series = {Lecture Notes in Informatics}, title = {Emergent Semantics in BibSonomy}, url = {http://www.kde.cs.uni-kassel.de/stumme/papers/2006/hotho2006emergent.pdf}, volume = {P-94}, year = 2006 } @article{pastor2001dynamical, author = {Pastor-Satorras, R. and V{\'a}zquez, A. and Vespignani, A.}, interhash = {a27ced257d69009a0d0d84ec8fe0b27c}, intrahash = {ac8378e4402c80d0f5fcce9ef6ac359f}, journal = {Physical Review Letters}, number = 25, pages = 258701, publisher = {APS}, title = {{Dynamical and correlation properties of the Internet}}, url = {http://scholar.google.de/scholar.bib?q=info:KLiz1q2axUQJ:scholar.google.com/&output=citation&hl=de&as_sdt=2000&ct=citation&cd=0}, volume = 87, year = 2001 } @article{cattuto2007network, author = {Cattuto, Ciro and Schmitz, Christoph and Baldassarri, Andrea and Servedio, Vito D. P. and Loreto, Vittorio and Hotho, Andreas and Grahl, Miranda and Stumme, Gerd}, editor = {Hoche, Susanne and Nürnberger, Andreas and Flach, Jürgen}, interhash = {fc5f2df61d28bc99b7e15029da125588}, intrahash = {da6c676c5664017247c7564fc247b190}, issn = {0921-7126}, journal = {AI Communications Journal, Special Issue on ``Network Analysis in Natural Sciences and Engineering''}, number = 4, pages = {245-262}, publisher = {IOS Press}, title = {Network Properties of Folksonomies}, url = {http://www.kde.cs.uni-kassel.de/stumme/papers/2007/cattuto2007network.pdf}, vgwort = {67}, volume = 20, year = 2007 } @article{newman01random, abstract = {Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.}, address = {Santa Fe Institute, 1399 Hyde Park Road, New Mexico 87501, USA.}, author = {Newman, M. E. and Strogatz, S. H. and Watts, D. J.}, citeulike-article-id = {48}, citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/11497662}, citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=11497662}, citeulike-linkout-2 = {http://arxiv.org/pdf/cond-mat/0007235}, interhash = {706d572ebbb2408b5a4ffa6978579dec}, intrahash = {a70982281644ecba5c38afd70cc5d123}, issn = {1539-3755}, journal = {Phys Rev E Stat Nonlin Soft Matter Phys}, month = {August}, number = {2 Pt 2}, posted-at = {2005-07-07 17:17:03}, priority = {0}, title = {Random graphs with arbitrary degree distributions and their applications.}, url = {http://view.ncbi.nlm.nih.gov/pubmed/11497662}, volume = 64, year = 2001 }