Online Social Networks (OSNs) have become an integral part of today's Web. Politicians, celebrities, revolutionists, and others use OSNs as a podium to deliver their message to millions of active web users. Unfortunately, in the wrong hands, OSNs can be used to run astroturf campaigns to spread misinformation and propaganda. Such campaigns usually start o� by in�ltrating a targeted OSN on a large scale. In this paper, we evaluate how vulnerable OSNs are to a large-scale in�ltration by socialbots: computer programs that control OSN accounts and mimic real users. We adopt a traditional web-based botnet design and built a Socialbot Network (SbN): a group of adaptive socialbots that are or- chestrated in a command-and-control fashion. We operated such an SbN on Facebook|a 750 million user OSN|for about 8 weeks. We collected data related to users' behav- ior in response to a large-scale in�ltration where socialbots were used to connect to a large number of Facebook users. Our results show that (1) OSNs, such as Facebook, can be in�ltrated with a success rate of up to 80%, (2) depending on users' privacy settings, a successful in�ltration can result in privacy breaches where even more users' data are exposed when compared to a purely public access, and (3) in prac- tice, OSN security defenses, such as the Facebook Immune System, are not e�ective enough in detecting or stopping a large-scale in�ltration as it occurs.

@inproceedings{boshmaf2011socialbot, author = {Boshmaf, Yazan and Muslukhov, Ildar and Beznosov, Konstantin and Ripeanu, Matei}, title = {The Socialbot Network: When Bots Socialize for Fame and Money}, booktitle = {Proc. of the Annual Computer Security Applications Conference 2011}, publisher = {ACM}, year = {2011}, url = {http://lersse-dl.ece.ubc.ca/record/264/files/ACSAC_2011.pdf}, keywords = {anaylsis, bots, facebook, network, socialbot, socialize, toread}, abstract = {Online Social Networks (OSNs) have become an integral part of today's Web. Politicians, celebrities, revolutionists, and others use OSNs as a podium to deliver their message to millions of active web users. Unfortunately, in the wrong hands, OSNs can be used to run astroturf campaigns to spread misinformation and propaganda. Such campaigns usually start o� by in�ltrating a targeted OSN on a large scale. In this paper, we evaluate how vulnerable OSNs are to a large-scale in�ltration by socialbots: computer programs that control OSN accounts and mimic real users. We adopt a traditional web-based botnet design and built a Socialbot Network (SbN): a group of adaptive socialbots that are or- chestrated in a command-and-control fashion. We operated such an SbN on Facebook|a 750 million user OSN|for about 8 weeks. We collected data related to users' behav- ior in response to a large-scale in�ltration where socialbots were used to connect to a large number of Facebook users. Our results show that (1) OSNs, such as Facebook, can be in�ltrated with a success rate of up to 80%, (2) depending on users' privacy settings, a successful in�ltration can result in privacy breaches where even more users' data are exposed when compared to a purely public access, and (3) in prac- tice, OSN security defenses, such as the Facebook Immune System, are not e�ective enough in detecting or stopping a large-scale in�ltration as it occurs.} }

%0 = inproceedings %A = Boshmaf, Yazan and Muslukhov, Ildar and Beznosov, Konstantin and Ripeanu, Matei %B = Proc. of the Annual Computer Security Applications Conference 2011 %D = 2011 %I = ACM %T = The Socialbot Network: When Bots Socialize for Fame and Money %U = http://lersse-dl.ece.ubc.ca/record/264/files/ACSAC_2011.pdf

@misc{text2006Mehler, author = {Mehler, A.}, title = {Text Linkage in the Wiki Medium-A comparative study}, editor = {Jussi, Karlgren}, booktitle = {Proceedings of the EACL 2006 Workshop on New Text-Wikis and blogs and other dynamic text sources}, year = {2006}, pages = {1-8}, url = {http://www.sics.se/jussi/newtext/working_notes/01_mehler.pdf}, keywords = {network, social, toread, wikipedia} }

%0 = misc %A = Mehler, A. %B = Proceedings of the EACL 2006 Workshop on New Text-Wikis and blogs and other dynamic text sources} %C = %D = 2006 %I = %T = Text Linkage in the Wiki Medium-A comparative study} %U = http://www.sics.se/jussi/newtext/working_notes/01_mehler.pdf

@inproceedings{transybil2009, author = {Tran, D.N. and Min, B. and Li, J. and Subramanian, L.}, title = {Sybil-resilient online content rating}, year = {2009}, url = {http://scholar.google.com/scholar.bib?q=info:YVSgj4tFvzEJ:scholar.google.com/&output=citation&hl=de&as_sdt=0&scfhb=1&ct=citation&cd=0}, keywords = {factors, network, social, toread} }

%0 = inproceedings %A = Tran, D.N. and Min, B. and Li, J. and Subramanian, L. %D = 2009 %T = Sybil-resilient online content rating %U = http://scholar.google.com/scholar.bib?q=info:YVSgj4tFvzEJ:scholar.google.com/&output=citation&hl=de&as_sdt=0&scfhb=1&ct=citation&cd=0

We study the social structure of Facebook "friendship" networks at one
ndred American colleges and universities at a single point in time, and we
amine the roles of user attributes - gender, class year, major, high school,
d residence - at these institutions. We investigate the influence of common
tributes at the dyad level in terms of assortativity coefficients and
gression models. We then examine larger-scale groupings by detecting
mmunities algorithmically and comparing them to network partitions based on
e user characteristics. We thereby compare the relative importances of
fferent characteristics at different institutions, finding for example that
mmon high school is more important to the social organization of large
stitutions and that the importance of common major varies significantly
tween institutions. Our calculations illustrate how microscopic and
croscopic perspectives give complementary insights on the social organization
universities and suggest future studies to investigate such phenomena
rther.

@misc{Traud2011, author = {Traud, Amanda L. and Mucha, Peter J. and Porter, Mason A.}, title = {Social Structure of Facebook Networks}, year = {2011}, note = {cite arxiv:1102.2166
mment: 82 pages (including many pages of tables), 8 multi-part figures,
"Facebook100" data used in this paper is publicly available at
http://people.maths.ox.ac.uk/~porterm/data/facebook100.zip}, url = {http://arxiv.org/abs/1102.2166}, keywords = {facebook, network, structure, toread}, abstract = { We study the social structure of Facebook "friendship" networks at one hundred American colleges and universities at a single point in time, and we examine the roles of user attributes - gender, class year, major, high school, and residence - at these institutions. We investigate the influence of common attributes at the dyad level in terms of assortativity coefficients and regression models. We then examine larger-scale groupings by detecting communities algorithmically and comparing them to network partitions based on the user characteristics. We thereby compare the relative importances of different characteristics at different institutions, finding for example that common high school is more important to the social organization of large institutions and that the importance of common major varies significantly between institutions. Our calculations illustrate how microscopic and macroscopic perspectives give complementary insights on the social organization at universities and suggest future studies to investigate such phenomena further. } }

%0 = misc %A = Traud, Amanda L. and Mucha, Peter J. and Porter, Mason A. %B = } %C = %D = 2011 %I = %T = Social Structure of Facebook Networks} %U = http://arxiv.org/abs/1102.2166

The rise of the social media sites, such as blogs, wikis, Digg and Flickr among others, underscores the transformation of the Web to a participatory medium in which users are collaboratively creating, evaluating and distributing information. The innovations introduced by social media has lead to a new paradigm for interacting with information, what we call 'social information processing'. In this paper, we study how social news aggregator Digg exploits social information processing to solve the problems of document recommendation and rating. First, we show, by tracking stories over time, that social networks play an important role in document recommendation. The second contribution of this paper consists of two mathematical models. The first model describes how collaborative rating and promotion of stories emerges from the independent decisions made by many users. The second model describes how a user's influence, the number of promoted stories and the user's social network, changes in time. We find qualitative agreement between predictions of the model and user data gathered from Digg.

@article{Lerman:2007p3955, author = {Lerman, Kristina}, title = {Social Information Processing in Social News Aggregation}, journal = {arXiv}, year = {2007}, url = {http://arxiv.org/abs/cs.CY/0703087}, keywords = {digg, dynamics, flickr, network, social, toread}, abstract = {The rise of the social media sites, such as blogs, wikis, Digg and Flickr among others, underscores the transformation of the Web to a participatory medium in which users are collaboratively creating, evaluating and distributing information. The innovations introduced by social media has lead to a new paradigm for interacting with information, what we call 'social information processing'. In this paper, we study how social news aggregator Digg exploits social information processing to solve the problems of document recommendation and rating. First, we show, by tracking stories over time, that social networks play an important role in document recommendation. The second contribution of this paper consists of two mathematical models. The first model describes how collaborative rating and promotion of stories emerges from the independent decisions made by many users. The second model describes how a user's influence, the number of promoted stories and the user's social network, changes in time. We find qualitative agreement between predictions of the model and user data gathered from Digg.} }

%0 = article %A = Lerman, Kristina %D = 2007 %T = Social Information Processing in Social News Aggregation %U = http://arxiv.org/abs/cs.CY/0703087

@inproceedings{1281280, author = {Xu, Xiaowei and Yuruk, Nurcan and Feng, Zhidan and Schweiger, Thomas A. J.}, title = {SCAN: a structural clustering algorithm for networks}, booktitle = {KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM}, address = {New York, NY, USA}, year = {2007}, pages = {824--833}, url = {http://portal.acm.org/citation.cfm?doid=1281192.1281280}, doi = {http://doi.acm.org/10.1145/1281192.1281280}, isbn = {978-1-59593-609-7}, keywords = {clustering, graph, network, toread} }

%0 = inproceedings %A = Xu, Xiaowei and Yuruk, Nurcan and Feng, Zhidan and Schweiger, Thomas A. J. %B = KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2007 %I = ACM %T = SCAN: a structural clustering algorithm for networks %U = http://portal.acm.org/citation.cfm?doid=1281192.1281280

To account for strong ageing characteristics of citation networks, we modify the PageRank algorithm by initially distributing random surfers exponentially with age, in favour of more recent publications. The output of this algorithm, which we call CiteRank, is interpreted as approximate traffic to individual publications in a simple model of how researchers find new information. We optimize parameters of our algorithm to achieve the best performance. The results are compared for two rather different citation networks: all American Physical Society publications between 1893 and 2003 and the set of high-energy physics theory (hep-th) preprints. Despite major differences between these two networks, we find that their optimal parameters for the CiteRank algorithm are remarkably similar. The advantages and performance of CiteRank over more conventional methods of ranking publications are discussed.

@article{1742-5468-2007-06-P06010, author = {Walker, Dylan and Xie, Huafeng and Yan, Koon-Kiu and Maslov, Sergei}, title = {Ranking scientific publications using a model of network traffic}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, year = {2007}, volume = {2007}, number = {06}, pages = {P06010}, url = {http://stacks.iop.org/1742-5468/2007/i=06/a=P06010}, keywords = {network, paper, publication, ranking, scientific, toread}, abstract = {To account for strong ageing characteristics of citation networks, we modify the PageRank algorithm by initially distributing random surfers exponentially with age, in favour of more recent publications. The output of this algorithm, which we call CiteRank, is interpreted as approximate traffic to individual publications in a simple model of how researchers find new information. We optimize parameters of our algorithm to achieve the best performance. The results are compared for two rather different citation networks: all American Physical Society publications between 1893 and 2003 and the set of high-energy physics theory (hep-th) preprints. Despite major differences between these two networks, we find that their optimal parameters for the CiteRank algorithm are remarkably similar. The advantages and performance of CiteRank over more conventional methods of ranking publications are discussed.} }

%0 = article %A = Walker, Dylan and Xie, Huafeng and Yan, Koon-Kiu and Maslov, Sergei %D = 2007 %T = Ranking scientific publications using a model of network traffic %U = http://stacks.iop.org/1742-5468/2007/i=06/a=P06010

We review our recent work on applying the Google PageRank algorithm to find scientific "gems" among all Physical Review publications, and its extension to CiteRank, to find currently popular research directions. These metrics provide a meaningful extension to traditionally-used importance measures, such as the number of citations and journal impact factor. We also point out some pitfalls of over-relying on quantitative metrics to evaluate scientific quality.

@misc{Maslov2009, author = {Maslov, Sergei and Redner, S.}, title = {Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation Networks}, year = {2009}, note = {cite arxiv:0901.2640 Comment: 3 pages, 1 figure, invited comment for the Journal of Neuroscience. The arxiv version is microscopically different from the published version}, url = {http://arxiv.org/abs/0901.2640}, keywords = {citation, index, network, pagerank, ranking, toread}, abstract = { We review our recent work on applying the Google PageRank algorithm to find scientific "gems" among all Physical Review publications, and its extension to CiteRank, to find currently popular research directions. These metrics provide a meaningful extension to traditionally-used importance measures, such as the number of citations and journal impact factor. We also point out some pitfalls of over-relying on quantitative metrics to evaluate scientific quality. } }

%0 = misc %A = Maslov, Sergei and Redner, S. %B = } %C = %D = 2009 %I = %T = Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation Networks} %U = http://arxiv.org/abs/0901.2640

@inproceedings{anagnostopoulos2011authority, author = {Anagnostopoulos, Aris and Brova, George and Terzi, Evimaria}, title = {Peer and Authority Pressure in Information-Propagation Models}, booktitle = {Proceedings of the ECML/PKDD 2011}, year = {2011}, keywords = {analysis, authority, bibsonomy, network, peer, toread} }

%0 = inproceedings %A = Anagnostopoulos, Aris and Brova, George and Terzi, Evimaria %B = Proceedings of the ECML/PKDD 2011 %D = 2011 %T = Peer and Authority Pressure in Information-Propagation Models

Zusammenfassung  Online Social Networks wie Xing.com oder Facebook.com gehören zu den am stärksten wachsenden Diensten im Internet. Im Jahr
08 nutzten geschätzte 580 Mio. Menschen weltweit diese Angebote. Entsprechend schnell haben sich Online Social Networksinnerhalb weniger Jahre von einem Nischenphänomen zu einem weltweiten Medium der IT-gestützten Kommunikation entwickelt. Insbesondereaufgrund stark wachsender Mitgliederzahlen entfalten Online Social Networks eine erhebliche gesellschaftliche und wirtschaftlicheBedeutung. Vor diesem Hintergrund ist es Ziel dieses Beitrags, Begriff und Eigenschaften, Entstehung und Entwicklung sowieNutzenpotenziale und Herausforderungen von Online Social Networks näher zu untersuchen.

@article{juliaonline, author = {Heidemann, Julia}, title = {Online Social Networks – Ein sozialer und technischer Überblick}, journal = {Informatik-Spektrum}, year = {2009}, pages = {--}, url = {http://dx.doi.org/10.1007/s00287-009-0367-0}, keywords = {info2.0, network, social, systems, toread}, abstract = {Zusammenfassung  Online Social Networks wie Xing.com oder Facebook.com gehören zu den am stärksten wachsenden Diensten im Internet. Im Jahr 2008 nutzten geschätzte 580 Mio. Menschen weltweit diese Angebote. Entsprechend schnell haben sich Online Social Networksinnerhalb weniger Jahre von einem Nischenphänomen zu einem weltweiten Medium der IT-gestützten Kommunikation entwickelt. Insbesondereaufgrund stark wachsender Mitgliederzahlen entfalten Online Social Networks eine erhebliche gesellschaftliche und wirtschaftlicheBedeutung. Vor diesem Hintergrund ist es Ziel dieses Beitrags, Begriff und Eigenschaften, Entstehung und Entwicklung sowieNutzenpotenziale und Herausforderungen von Online Social Networks näher zu untersuchen.} }

%0 = article %A = Heidemann, Julia %D = 2009 %T = Online Social Networks – Ein sozialer und technischer Überblick %U = http://dx.doi.org/10.1007/s00287-009-0367-0

Networks portray a multitude of interactions through which people meet, ideas
e spread, and infectious diseases propagate within a society. Identifying the
st efficient "spreaders" in a network is an important step to optimize the
e of available resources and ensure the more efficient spread of information.
re we show that, in contrast to common belief, the most influential spreaders
a social network do not correspond to the best connected people or to the
st central people (high betweenness centrality). Instead, we find: (i) The
st efficient spreaders are those located within the core of the network as
entified by the k-shell decomposition analysis. (ii) When multiple spreaders
e considered simultaneously, the distance between them becomes the crucial
rameter that determines the extend of the spreading. Furthermore, we find
at- in the case of infections that do not confer immunity on recovered
dividuals- the infection persists in the high k-shell layers of the network
der conditions where hubs may not be able to preserve the infection. Our
alysis provides a plausible route for an optimal design of efficient
ssemination strategies.

@misc{Kitsak2010, author = {Kitsak, Maksim and Gallos, Lazaros K. and Havlin, Shlomo and Liljeros, Fredrik and Muchnik, Lev and Stanley, H. Eugene and Makse, Hernan A.}, title = {Identifying influential spreaders in complex networks}, year = {2010}, note = {cite arxiv:1001.5285
mment: 31 pages, 12 figures}, url = {http://arxiv.org/abs/1001.5285}, keywords = {analysis, centrality, network, social, toread}, abstract = { Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society. Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, the most influential spreaders in a social network do not correspond to the best connected people or to the most central people (high betweenness centrality). Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extend of the spreading. Furthermore, we find that-- in the case of infections that do not confer immunity on recovered individuals-- the infection persists in the high k-shell layers of the network under conditions where hubs may not be able to preserve the infection. Our analysis provides a plausible route for an optimal design of efficient dissemination strategies. } }

%0 = misc %A = Kitsak, Maksim and Gallos, Lazaros K. and Havlin, Shlomo and Liljeros, Fredrik and Muchnik, Lev and Stanley, H. Eugene and Makse, Hernan A. %B = } %C = %D = 2010 %I = %T = Identifying influential spreaders in complex networks} %U = http://arxiv.org/abs/1001.5285

Abstract  We have designed a highly versatile badge system to facilitate a variety of interaction at large professional or social events
d serve as a platform for conducting research into human dynamics. The badges are equipped with a large LED display, wirelessinfrared and radio frequency networking, and a host of sensors to collect data that we have used to develop features and algorithmsaimed at classifying and predicting individual and group behavior. This paper overviews our badge system, describes the interactionsand capabilities that it enabled for the wearers, and presents data collected over several large deployments. This data isanalyzed to track and socially classify the attendees, predict their interest in other people and demonstration installations,profile the restlessness of a crowd in an auditorium, and otherwise track the evolution and dynamics of the events at whichthe badges were run.

@article{joseph2010identifying, author = {Paradiso, Joseph and Gips, Jonathan and Laibowitz, Mathew and Sadi, Sajid and Merrill, David and Aylward, Ryan and Maes, Pattie and Pentland, Alex}, title = {Identifying and facilitating social interaction with a wearable wireless sensor network}, journal = {Personal and Ubiquitous Computing}, year = {2010}, volume = {14}, number = {2}, pages = {137--152}, url = {http://dx.doi.org/10.1007/s00779-009-0239-2}, keywords = {network, rfid, toread}, abstract = {Abstract  We have designed a highly versatile badge system to facilitate a variety of interaction at large professional or social events and serve as a platform for conducting research into human dynamics. The badges are equipped with a large LED display, wirelessinfrared and radio frequency networking, and a host of sensors to collect data that we have used to develop features and algorithmsaimed at classifying and predicting individual and group behavior. This paper overviews our badge system, describes the interactionsand capabilities that it enabled for the wearers, and presents data collected over several large deployments. This data isanalyzed to track and socially classify the attendees, predict their interest in other people and demonstration installations,profile the restlessness of a crowd in an auditorium, and otherwise track the evolution and dynamics of the events at whichthe badges were run.} }

%0 = article %A = Paradiso, Joseph and Gips, Jonathan and Laibowitz, Mathew and Sadi, Sajid and Merrill, David and Aylward, Ryan and Maes, Pattie and Pentland, Alex %D = 2010 %T = Identifying and facilitating social interaction with a wearable wireless sensor network %U = http://dx.doi.org/10.1007/s00779-009-0239-2

@inproceedings{conf/kdd/BackstromHKL06, author = {Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang}, title = {Group formation in large social networks: membership, growth, and evolution.}, editor = {Eliassi-Rad, Tina and Ungar, Lyle H. and Craven, Mark and Gunopulos, Dimitrios}, booktitle = {KDD}, publisher = {ACM}, year = {2006}, pages = {44-54}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06}, isbn = {1-59593-339-5}, keywords = {social, toread, evolution, community, network} }

%0 = inproceedings %A = Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang %B = KDD %D = 2006 %I = ACM %T = Group formation in large social networks: membership, growth, and evolution. %U = http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06

@inproceedings{jin:07:eswc, author = {Jin, YingZi and Matsuo, Yutaka and Ishizuka, Mitsuru}, title = {Extracting Social Networks among Various Entities on the Web}, editor = {Franconi, Enrico and Kifer, Michael and May, Wolfgang}, booktitle = {Proceedings of the European Semantic Web Conference, ESWC2007}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, year = {2007}, volume = {4519}, url = {http://www.eswc2007.org/pdf/eswc07-jin.pdf}, keywords = {extraction, network, relation, social, toread} }

%0 = inproceedings %A = Jin, YingZi and Matsuo, Yutaka and Ishizuka, Mitsuru %B = Proceedings of the European Semantic Web Conference, ESWC2007 %D = 2007 %I = Springer-Verlag %T = Extracting Social Networks among Various Entities on the Web %U = http://www.eswc2007.org/pdf/eswc07-jin.pdf

We express community detection as an inference problem of determining the
st likely arrangement of communities. We then apply belief propagation and
an-field theory to this problem, and show that this leads to fast, accurate
gorithms for community detection.

@misc{citeulike:591709, author = {Hastings, M. B.}, title = {Community Detection as an Inference Problem}, year = {2006}, url = {http://arxiv.org/abs/cond-mat/0604429}, keywords = {toread, community, network}, abstract = {We express community detection as an inference problem of determining the most likely arrangement of communities. We then apply belief propagation and mean-field theory to this problem, and show that this leads to fast, accurate algorithms for community detection.} }

%0 = misc %A = Hastings, M. B. %B = } %C = %D = 2006 %I = %T = Community Detection as an Inference Problem} %U = http://arxiv.org/abs/cond-mat/0604429

A dynamic network is a special type of network composed of connected transactors which have repeated evolving interaction. Data on large dynamic networks such as telecommunications networks and the Internet are pervasive. However, representing dynamic networks in a manner that is conducive to efficient large-scale analysis is a challenge. In this article, we represent dynamic graphs using a data structure introduced in an earlier article. We advocate their representation because it accounts for the evolution of relationships between transactors through time, mitigates noise at the local transactor level, and allows for the removal of stale relationships. Our work improves on their heuristic arguments by formalizing the representation with three tunable parameters. In doing this, we develop a generic framework for evaluating and tuning any dynamic graph. We show that the storage saving approximations involved in the representation do not affect predictive performance, and typically improve it. We motivate our approach using a fraud detection example from the telecommunications industry, and demonstrate that we can outperform published results on the fraud detection task. In addition, we present a preliminary analysis on Web logs and e-mail networks.

@article{Hill:September_2006:1061-8600:584, author = {Hill, Shawndra and Agarwal, Deepak K. and Bell, Robert and Volinsky, Chris}, title = {Building an Effective Representation for Dynamic Networks}, journal = {Journal of Computational & Graphical Statistics}, year = {2006}, volume = {15}, pages = {584-608(25)}, url = {http://www.ingentaconnect.com/content/asa/jcgs/2006/00000015/00000003/art00006}, doi = {doi:10.1198/106186006X139162}, keywords = {data, network, representation, toread}, abstract = {A dynamic network is a special type of network composed of connected transactors which have repeated evolving interaction. Data on large dynamic networks such as telecommunications networks and the Internet are pervasive. However, representing dynamic networks in a manner that is conducive to efficient large-scale analysis is a challenge. In this article, we represent dynamic graphs using a data structure introduced in an earlier article. We advocate their representation because it accounts for the evolution of relationships between transactors through time, mitigates noise at the local transactor level, and allows for the removal of stale relationships. Our work improves on their heuristic arguments by formalizing the representation with three tunable parameters. In doing this, we develop a generic framework for evaluating and tuning any dynamic graph. We show that the storage saving approximations involved in the representation do not affect predictive performance, and typically improve it. We motivate our approach using a fraud detection example from the telecommunications industry, and demonstrate that we can outperform published results on the fraud detection task. In addition, we present a preliminary analysis on Web logs and e-mail networks. } }

%0 = article %A = Hill, Shawndra and Agarwal, Deepak K. and Bell, Robert and Volinsky, Chris %D = 2006 %T = Building an Effective Representation for Dynamic Networks %U = http://www.ingentaconnect.com/content/asa/jcgs/2006/00000015/00000003/art00006

Similarity breeds connection. This principle-the homophily principle-structures network ties of every type, including marriage, friendship, work, advice, support, information transfer, exchange, comembership, and other types of relationship. The result is that people's personal networks are homogeneous with regard to many sociodemographic, behavioral, and intrapersonal characteristics. Homophily limits people's social worlds in a way that has powerful implications for the information they receive, the attitudes they form, and the interactions they experience. Homophily in race and ethnicity creates the strongest divides in our personal environments, with age, religion, education, occupation, and gender following in roughly that order. Geographic propinquity, families, organizations, and isomorphic positions in social systems all create contexts in which homophilous relations form. Ties between nonsimilar individuals also dissolve at a higher rate, which sets the stage for the formation of niches (localized positions) within social space. We argue for more research on: (a) the basic ecological processes that link organizations, associations, cultural communities, social movements, and many other social forms; (b) the impact of multiplex ties on the patterns of homophily; and (c) the dynamics of network change over time through which networks and other social entities co-evolve.

@misc{ieKey, author = {McPherson, Miller and Smith-Lovin, Lynn and Cook, James M.}, title = {Birds of a Feather: Homophily in Social Networks }, journal = {Annual Review of Sociology}, year = {2001}, volume = {27}, pages = {415-444}, note = {This article consists of 30 page(s)}, url = {http://arjournals.annualreviews.org/doi/pdf/10.1146/annurev.soc.27.1.415}, keywords = {network, speed, toread}, abstract = {Similarity breeds connection. This principle-the homophily principle-structures network ties of every type, including marriage, friendship, work, advice, support, information transfer, exchange, comembership, and other types of relationship. The result is that people's personal networks are homogeneous with regard to many sociodemographic, behavioral, and intrapersonal characteristics. Homophily limits people's social worlds in a way that has powerful implications for the information they receive, the attitudes they form, and the interactions they experience. Homophily in race and ethnicity creates the strongest divides in our personal environments, with age, religion, education, occupation, and gender following in roughly that order. Geographic propinquity, families, organizations, and isomorphic positions in social systems all create contexts in which homophilous relations form. Ties between nonsimilar individuals also dissolve at a higher rate, which sets the stage for the formation of niches (localized positions) within social space. We argue for more research on: (a) the basic ecological processes that link organizations, associations, cultural communities, social movements, and many other social forms; (b) the impact of multiplex ties on the patterns of homophily; and (c) the dynamics of network change over time through which networks and other social entities co-evolve.} }

%0 = misc %A = McPherson, Miller and Smith-Lovin, Lynn and Cook, James M. %B = } %C = %D = 2001 %I = %T = Birds of a Feather: Homophily in Social Networks } %U = http://arjournals.annualreviews.org/doi/pdf/10.1146/annurev.soc.27.1.415

Networks are ubiquitous in science and have become a focal point for
scussion in everyday life. Formal statistical models for the analysis of
twork data have emerged as a major topic of interest in diverse areas of
udy, and most of these involve a form of graphical representation.
obability models on graphs date back to 1959. Along with empirical studies in
cial psychology and sociology from the 1960s, these early works generated an
tive network community and a substantial literature in the 1970s. This effort
ved into the statistical literature in the late 1970s and 1980s, and the past
cade has seen a burgeoning network literature in statistical physics and
mputer science. The growth of the World Wide Web and the emergence of online
tworking communities such as Facebook, MySpace, and LinkedIn, and a host of
re specialized professional network communities has intensified interest in
e study of networks and network data. Our goal in this review is to provide
e reader with an entry point to this burgeoning literature. We begin with an
erview of the historical development of statistical network modeling and then
introduce a number of examples that have been studied in the network
terature. Our subsequent discussion focuses on a number of prominent static
d dynamic network models and their interconnections. We emphasize formal
del descriptions, and pay special attention to the interpretation of
rameters and their estimation. We end with a description of some open
oblems and challenges for machine learning and statistics.

@misc{goldenberg2009survey, author = {Goldenberg, Anna and Zheng, Alice X and Fienberg, Stephen E and Airoldi, Edoardo M}, title = {A survey of statistical network models}, year = {2009}, note = {cite arxiv:0912.5410Comment: 96 pages, 14 figures, 333 references}, url = {http://arxiv.org/abs/0912.5410}, keywords = {models, network, sota, survey, topic, toread}, abstract = {Networks are ubiquitous in science and have become a focal point fordiscussion in everyday life. Formal statistical models for the analysis ofnetwork data have emerged as a major topic of interest in diverse areas ofstudy, and most of these involve a form of graphical representation.Probability models on graphs date back to 1959. Along with empirical studies insocial psychology and sociology from the 1960s, these early works generated anactive network community and a substantial literature in the 1970s. This effortmoved into the statistical literature in the late 1970s and 1980s, and the pastdecade has seen a burgeoning network literature in statistical physics andcomputer science. The growth of the World Wide Web and the emergence of onlinenetworking communities such as Facebook, MySpace, and LinkedIn, and a host ofmore specialized professional network communities has intensified interest inthe study of networks and network data. Our goal in this review is to providethe reader with an entry point to this burgeoning literature. We begin with anoverview of the historical development of statistical network modeling and thenwe introduce a number of examples that have been studied in the networkliterature. Our subsequent discussion focuses on a number of prominent staticand dynamic network models and their interconnections. We emphasize formalmodel descriptions, and pay special attention to the interpretation ofparameters and their estimation. We end with a description of some openproblems and challenges for machine learning and statistics.} }

%0 = misc %A = Goldenberg, Anna and Zheng, Alice X and Fienberg, Stephen E and Airoldi, Edoardo M %B = } %C = %D = 2009 %I = %T = A survey of statistical network models} %U = http://arxiv.org/abs/0912.5410

We investigate a simple generative model for network formation. The model is designed to describe the growth of networks of kinship, trading, corporate alliances, or autocatalytic chemical reactions, where feedback is an essential element of network growth. The underlying graphs in these situations grow via a competition between cycle formation and node addition. After choosing a given node, a search is made for another node at a suitable distance. If such a node is found, a link is added connecting this to the original node, and increasing the number of cycles in the graph; if such a node cannot be found, a new node is added, which is linked to the original node. We simulate this algorithm and find that we cannot reject the hypothesis that the empirical degree distribution is a q-exponential function, which has been used to model long-range processes in nonequilibrium statistical mechanics.

@misc{white-2005, author = {White, Douglas R. and Kejzar, Natasa and Tsallis, Constantino and Farmer, Doyne and White, Scott}, title = {A generative model for feedback networks}, year = {2005}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0508028}, keywords = {model, network, toread}, abstract = { We investigate a simple generative model for network formation. The model is designed to describe the growth of networks of kinship, trading, corporate alliances, or autocatalytic chemical reactions, where feedback is an essential element of network growth. The underlying graphs in these situations grow via a competition between cycle formation and node addition. After choosing a given node, a search is made for another node at a suitable distance. If such a node is found, a link is added connecting this to the original node, and increasing the number of cycles in the graph; if such a node cannot be found, a new node is added, which is linked to the original node. We simulate this algorithm and find that we cannot reject the hypothesis that the empirical degree distribution is a q-exponential function, which has been used to model long-range processes in nonequilibrium statistical mechanics.} }

%0 = misc %A = White, Douglas R. and Kejzar, Natasa and Tsallis, Constantino and Farmer, Doyne and White, Scott %B = } %C = %D = 2005 %I = %T = A generative model for feedback networks} %U = http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0508028