Archive for April, 2009

How to model social nets – Exponential random graph models

Thursday, April 30th, 2009

Today we had a talk by Cyrus Hall of the University of Lugano. He proposed a p2p sampling algorithm to allow p2p admins to monitor and maintain their nets. He evaluated his algorithm against synthetic p2p topologies, which included kleinberg’s social net model and barabasi’s. For years now, it has been assumed that those traditional models reflect real social nets. However, after the talk, Damon pointed at the existence of exponential random graph models. Traditional models do not assume the knowledge of any global property (e.g., clustering coefficient) of a social network – they do the modeling without any input. By contrast, random graph models are able to model any type of social network on input of the network’s global properties. here is a paper titled “Recent developments in exponential random graph (p*) models for social networks” (pdf). Enjoy!

Temporal Collaborative Filtering

Tuesday, April 28th, 2009

As part of my recent work on collaborative filtering (CF), I’ve been examining the role that time plays in recommender systems. To date, the most notable use of temporal information (if you’re familiar with the Netflix prize) is that researchers are using time(stamps) to inch their way closer to the million dollar reward. The idea is to use how user-ratings vary according to, for example, the day of the week they were input in order to better predict the probe (and more importantly, the qualifying) datasets. I suppose my only criticism here is that once the million dollars has been won, nobody is going to implement and deploy this aspect of the algorithm (unless you are prepared to update your recommendations every day?) – since, in practice, we do not know when users are going to rate items.

In the context of my work, I’ve been looking at 2 areas; the effect of time on (1) similarity between users (RecSys ’08), and (2) the recommender system itself. Here’s a brief summary of (2): (more…)

Sociologists and data miners come together to advance social computing

Tuesday, April 28th, 2009

(from here) From: Gregory Piatetsky-Shapiro; SBP09 Second Workshop on Social Computing, Behavioral Modeling, and Prediction

  • keynote presentation by Phillip Bonacich (UCLA, Emeritus), about Power and Exploitation in Exchange Networks: A Social-Psychological Model.
  • Mary Lou Maher (NSF) talked about Research Challenges for Computationally Enabled Social and Collective Intelligence.She gave a number of collective intelligence examples, including open source systems, recommender systems, search engines, and Wikipedia.
  • William H. Batchelder, a leading expert on psychology and social sciences, talked about Cultural Consensus Theory, which is an approach to pooling information from different sources.Batchelder showed that a social network model, with a good deal of math, a Bayesian formulation and MCMC methods, can be used to estimate the consensus answers.
  • Shade Shutters (ASU) talked about Punishment, Rational Expectations, and Relative Payoffs.
  • Many posters were presented during a workshop dinner the first night 
  • On the second workshop day, Alex Penland from MIT Media Lab gave a keynote talk on Reality Mining: From Profiles and Demographics to Behavior .Dr. Penland is very sensitive to privacy issues and says these sensors should not be used to spy on employees. He suggests that deployment should be on voluntary data with individuals owning the data and have the opportunity to review their data each day. Learning can be done effectively from anonymized profiles. Dr. Penland company Sense Networks is now commercializing these applications in macrosense™ and Citysense™

RecSys Twibe

Monday, April 27th, 2009

If you are on Twitter, feel free to join our newly formed recommender system-interest twibe:

Yahoo! BOSS

Wednesday, April 22nd, 2009

BOSS (Build your Own Search Service) is Yahoo!’s open search web services platform. … Developers, start-ups, and large Internet companies can use BOSS to build and launch web-scale search products that utilize the entire Yahoo! Search index.

Open-source Design for Architecture and Furniture

Sunday, April 19th, 2009

Open-source design for:

1) Architecture (by UCL alumnus Cameron Sinclair)

2) Furniture
High-End Furniture Goes Open Source. The autocad files are here – download & personalize them, find the nearest laser cutter, and  make yourself a cool table ;-)

Collaborative Filtering for

Friday, April 17th, 2009

A post on digg’s techblog on Digg’s Collaborative Filtering mechanism.

two great talks on Thursday

Tuesday, April 14th, 2009

(from Brad Karp’s email)

Dr Ranveer Chandra
Microsoft Research

[Talk title TBA]

10:30 AM, Thursday, 16th April
Roberts G06 (Sir Ambrose Fleming LT)

Bio: Ranveer Chandra is a researcher in the Networking Research Group at Microsoft Research. He completed his undergraduate studies from the Indian Institute of Technology, Kharagpur and a PhD in Computer Science from Cornell University. He was the recipient of the Microsoft Graduate Research Fellowship during his PhD and his dissertation on VirtualWiFi was nominated by Cornell for the ACM Dissertation Award. VirtualWiFi has been downloaded more than 100,000 times and is the third most downloaded software ever to be released by Microsoft Research. Ranveer has authored more than 25 research papers and filed more than 30 patents. He is active in the networking and mobile systems community, and has served on the program committees of several conferences.

Professor Michael Mitzenmacher
Harvard University

Some Results on Coding for Flash Memory

11:15 AM, Thursday, 16th April
Roberts G06 (Sir Ambrose Fleming LT)

Abstract: Flash memory is rapidly becoming the technology of choice for storage in several settings. But flash memory behaves differently than other memory systems, making us rethink the basic ways we represent data. In this talk we’ll consider the question of how to code data for flash memory systems. Although our framework will be primarily theoretical, it will shed light on some of the basic issues underlying the use of flash memory systems, including what considerations need to be kept in mind when designing algorithms or data structures for such systems.

Bio: Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 140 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes shared the 2002 IEEE Information Theory Society Best Paper Award. His textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press. This year, he is serving as chair of STOC 2009 and on the PC of SIGCOMM 2009.

Michael Mitzenmacher graduated summa cum laude with a degree in mathematics and computer science from Harvard in 1991. After studying math for a year in Cambridge, England, on the Churchill Scholarship, he obtained his Ph. D. in computer science at U.C. Berkeley in 1996. He then worked at Digital Systems Research Center until joining the Harvard faculty in 1999.

Studying Social Tagging and Folksonomy: A Review and Framework

Tuesday, April 14th, 2009

paper (pdf) by J. Trant, University of Toronto

Abstract:  This paper reviews research into social tagging and folksonomy (as reflected in about 180 sources published through December 2007). Methods of researching the contribution of social tagging and folksonomy are described, and outstanding research questions are presented. This is a new area of research, where theoretical perspectives and relevant research methods are only now being defined. This paper provides a framework for the study of folksonomy, tagging and social tagging systems. Three broad approaches are identified, focusing first, on the folksonomy itself (and the role of tags in indexing and retrieval); secondly, on tagging (and the behaviour of users); and thirdly, on the nature of social tagging systems (as socio-technical frameworks).

I know whr U R!

Wednesday, April 8th, 2009

“Albert-László Barabási and colleagues monitored 100,000 users for 6 months and recorded the location of the cell phone tower that transmitted each call or text message. The team found that:

  • most people stayed close to home, and a select few regularly took long trips. … regardless of how mobile they were, people returned over and over to a few top locations with similar probability. For example, two users would have roughly the same chance of being found in their third-favorite spots, whether it was the gym or the theater. These hangouts were often located near the path between their top two destinations–usually home and work
  • most people traveled very short distances most of the time, while some traveled great distances.
  • each individual’s data fit into the same mathematical model—a type of power law—that predicts the probability of finding a person in a certain location. That probability distribution is dependent on an individual’s average travel distance and decreases the further he or she roams. Human mobility and how we travel is so amazingly complex,” says Max Planck’s Brockmann. “What is very strange is that despite this complexity, all the traveling behavior can be accounted for by very simple mathematical laws.”

Potential applications: traffic forecasting and urban planning.

Putting a Price on Social Connections

Wednesday, April 8th, 2009

From today’s Business Week:

Why weak ties aren’t always strong. “Researchers at IBM and MIT have found that certain e-mail connections and patterns at work correlate with higher revenue production … they used mathematical formulas to analyze the e-mail traffic, address books, and buddy lists of 2,600 IBM consultants over the course of a year. … They compared the communication patterns with performance, as measured by billable hours. They found that consultants with weak ties to a number of managers produced $98 per month less than average. Why? Those employees may move more slowly as they process “conflicting demands from different managers,” the study’s authors write. They suffer from “too many cooks in the kitchen.”

How to introduce people (matchmaking). They also analyzed methods to introduce employees to colleagues they haven’t yet met (to incent people to participate). … “Geyer and his team are digging for signs of shared interests and behaviors among their colleagues. …In their matchmaking efforts, the IBM team tried a variety of approaches. One used a tool favored by Facebook, recommending friends of common friends. Others analyzed the subjects and themes of employees’ postings on Beehive, words they use, and patents they’ve filed. As expected, some of the systems lined up workers with colleagues they already knew. Others were better at unearthing unknowns. But fewer of them turned out to be good matches. To the frustration of the researchers, some of the workers noted that recommendations looked good, yet they didn’t bother contacting the people. “They put them aside for future reference,” Geyer says. “

Stanford University’s iPhone development course free online

Tuesday, April 7th, 2009

From Alex  Kerr on momolondon:”I thought this might be of interest to any developers on this list who are interested in learning to develop for the iPhone, particularly those non-corporate folks (e.g. students etc) who are on lower budgets. Stanford University have just started a new taught iPhone development class this semester and are putting it all up on iTunesU for free (at the same speed as the course is taught), and some of the material is available on the ordinary website.More details here


Mapping Social Networks (with APIs)

Monday, April 6th, 2009

There seem to be many reasons why people connect online. For example, on Twitter, I have connected to friends, colleagues, family, people I have met at conferences (or simply know from some of the work),  and a couple celebrities (like Tom Waits). These few reasons encompass a largely incomplete list of why two people may connect on a social network; of course, understanding why people connect to each other would give insight into suggesting new connections for people to make… (more…)

Our Department – CS UCL

Thursday, April 2nd, 2009

Few videos featuring our colleagues

Across the Department:

In the Software Systems group:

In the Networks Group:

More videos here.

DemocraBus (crowdsource bus driving): Genius!

Thursday, April 2nd, 2009

Yesterday I was watching Genius and I loved it!!!!!! Members of the public write to the comedian Dave Gorman with their funny ideas. Then Dave gets a guest on the show to decide if the ideas are Genius, or not.”

Brendan put forward a brilliant idea: how to crowdsource bus driving (1 and half minute of madness!) – every passenger has a steering wheel and the direction of the bus is determined by what the majority of passengers tell it to do. Unfortunately, it got the thumbs down