Detecting Patterns in Complex Social Networks 167
Roland Piquepaille writes "So-called social networking is very popular these days, as show the proliferation of services like Friendster, Orkut and dozens of others. But do the companies behind these services have any idea of what is hidden inside their complicated networks? When these networks reach a size of millions of users, it's not an easy task. A researcher at the University of Michigan is trying to help, with a new method for uncovering patterns in complicated networks, from football conferences to food webs. This overview contains more details and references about this non-traditional method. It also includes a spectacular representation of the Internet and another image showing a food web at Little Rock Lake."
Re: slashdotting - mirror of article text (Score:5, Informative)
SEATTLE---The world is full of complicated networks that scientists would like to better understand---human social systems, for example, or food webs in nature. But discerning patterns of organization in such vast, complex systems is no easy task.
"The structure of those networks can tell you quite a lot about how the systems work, but they're far too big to analyze by just putting dots on a piece of paper and drawing lines to connect them," said Mark Newman, an assistant professor of physics and complex systems at the University of Michigan.
One challenge in making sense of a large network is finding clumps---or communities---of members that have something in common, such as Web pages that are all about the same topic, people that socialize together or animals that eat the same kind of food. Newman and collaborator Michelle Girvan, a postdoctoral fellow at the Santa Fe Institute in Santa Fe, New Mexico, have developed a new method for finding communities that reveals a lot about the structure of large, complex networks. Newman will discuss the method and its applications Feb. 15 at the annual meeting of the American Association for the Advancement of Science in Seattle.
"The way most people have approached the problem is to look for the clumps themselves---to look for things that are joined together strongly," said Newman. "We decided to approach it from the other end," by searching out and then eliminating the links that join clumps together. "When we remove those from the network, what we're left with is the clumps."
The researchers tested their method on several networks for which the structure was already known---college football conferences, for example. In college football, teams in the same conference face off more frequently than teams in different conferences. When inter-conference games do occur, they're more likely to be between teams that are geographically close together than between teams that are far apart. Plugging in information on frequency of games between pairs of teams in the 2000 regular season, Newman and Girvan tested their method to see if it could correctly sort the colleges into conferences. "There were a few cases where it made mistakes, but it got well over 90 percent of them right," said Newman. "It gave us the structure we were expecting, so that was encouraging."
Newman and Girvan---and other researchers who've learned about their work---have gone on to apply the technique to systems where the structure is not as well understood, looking at everything from networks of Spanish language web logs to communities of early jazz musicians to a food web of marine organisms living in Chesapeake Bay.
"Networks and other systems that we study are becoming increasingly large and complicated these days," said Newman. "New methods like this help us to make sense of what we see and to understand better how things work."
###
For more information:
Mark Newman -- http://www-personal.umich.edu/~mejn/
American Association for the Advancement of Science -- http://www.aaas.org/
Santa Fe Institute -- http://www.santafe.edu/
Interesting but hardly new (Score:4, Informative)
Link to paper (Score:4, Informative)
Re:Role-Based Relationship Weights (Score:5, Informative)
The problem with this is the classic meta-data problem: how do you get users to enter in a sufficient amount of meaninful information about their peers?
The simple approach (and also the most innaccurate/flawed) is the binary status of "friend / non-friend" which has the drawbacks you mention.
But a much more detailed and expressive syntax would be incredibly cumbersome. For every person in your social network you would need to answer the detailed questionaire: "is this person a friend acquaintance. Is the friendship activity based, personal, business, etc." ad infinitum.
And unless everyone responded with completeness, the validity of any given link expressed between two people could vary greatly.
I'm a big fan of the implicit approach, and the research mentioned above goes a little ways towards implictly identifying and categorizing the nature of links between peers in a social network.
If a system could observe your interactions with others via email, phone, web communities, etc. (and preserve the privacy of such information - but thats another discussion) then the need for explicitly defining this social metadata would be reduced, as many of the aspects of social interactions could be inferred implicitly without bothering the user to enter (partial) information themselves.
There is a lot of progress to be made in this space; hopefully it will happen soon
see social network maps online (Score:2, Informative)
Social dynamics in Open Source Groups (Score:1, Informative)
Six degrees of separation (Score:2, Informative)
This was first proposed in 1967 by social psychologist Stanley Milgram [stanleymilgram.com], (in)famous for his shocking experiments [wikipedia.org] on human obedience, which inspired Peter Gabriel [petergabriel.com] to create the subversive sing-along "We Do What We're Told [seeklyrics.com]", a.k.a. "Milgram's 37 [solsburyhill.org]".
This paragraph brought you by a flock of hyperlinking free associators with Erds number [oakland.edu] 4.
websites that may enlighten about social networks (Score:2, Informative)
INSNA is the professional association for researchers interested in social network analysis.
http://www.casos.cs.cmu.edu/
CASOS brings together computer science, dynamic network analysis and the empirical study of complex socio-technical systems. Computational and social network techniques are combined to develop a better understanding of the fundamental principles of organizing, coordinating, managing and destabilizing systems of intelligent adaptive agents (human and artificial) engaged in real tasks at the team, organizational or social level. Whether the research involves the development of metrics, theories, computer simulations, toolkits, or new data analysis techniques advances in computer science are combined with a deep understanding of the underlying cognitive, social, political, business and policy issues.
http://www.cmu.edu/joss/
The Journal of Social Structure (JoSS) is an electronic journal of the International Network for Social Network Analysis (INSNA). It is designed to facilitate timely dissemination of state-of-the-art results in the interdisciplinary research area of social structure. It publishes empirical, theoretical and methodological articles.
JoSS publishes manuscripts that are focused on social structure-on the patterning of social linkages among actors. These actors could be comprised of different types or levels or analysis, such as animals, humans, artificial agents, groups or organizations. INSNA was founded on the premise that the behavior and lives of social entities are affected by their position in the overall social structure. By examining the etiology and consequences of structural forms overall, of the location of entities within these structures, and of the formation and dynamics of ties that make up these structures, INSNA hopes to learn about the parts of behavior that are uniquely social.
http://www.sciencedirect.com/science?_ob=JournalU
Publication of social networks papers.
Re:Slices of a datawarehouse? (Score:5, Informative)
What is interesting actually is NOT the clumps (the paper is wrong), but the (possibly heterogeneous, multi-modal and dynamic) networks and their various measurements that could reveal lots of things.
The parent is right in pointing a possible method of extracting the results, but ignores how one constructs the data warehouse in the first place and the significance of networks -- especially the social and dynamic ones -- instead of data warehouse, both of which are not trivial problems.
Several websites may enlighten those who are interested in probing social networks deeper:
http://www.sfu.ca/~insna/
INSNA is the professional association for researchers interested in social network analysis.
http://www.casos.cs.cmu.edu/
CASOS brings together computer science, dynamic network analysis and the empirical study of complex socio-technical systems. Computational and social network techniques are combined to develop a better understanding of the fundamental principles of organizing, coordinating, managing and destabilizing systems of intelligent adaptive agents (human and artificial) engaged in real tasks at the team, organizational or social level. Whether the research involves the development of metrics, theories, computer simulations, toolkits, or new data analysis techniques advances in computer science are combined with a deep understanding of the underlying cognitive, social, political, business and policy issues.
http://www.cmu.edu/joss/
The Journal of Social Structure (JoSS) is an electronic journal of the International Network for Social Network Analysis (INSNA). It is designed to facilitate timely dissemination of state-of-the-art results in the interdisciplinary research area of social structure. It publishes empirical, theoretical and methodological articles.
JoSS publishes manuscripts that are focused on social structure-on the patterning of social linkages among actors. These actors could be comprised of different types or levels or analysis, such as animals, humans, artificial agents, groups or organizations. INSNA was founded on the premise that the behavior and lives of social entities are affected by their position in the overall social structure. By examining the etiology and consequences of structural forms overall, of the location of entities within these structures, and of the formation and dynamics of ties that make up these structures, INSNA hopes to learn about the parts of behavior that are uniquely social.
http://www.sciencedirect.com/science?_ob=JournalU
Publication of social networks papers.
freindship (Score:2, Informative)
If you want the real scoop on social networks... (Score:5, Informative)
Furthermore, read a few books on emergence (like Kevin Kelly's "Out of Control" [google.com]). Might as well also pick up and read Wolfram's "A New Kind of Science" [google.com]...
I have said it before and I will say it again: Taken together, the knowledge within these three books could very well lead to some amazing breakthroughs in many of the sciences, in particular cognitive sciences and genetics. Even if some of the theories prove to be wrong, I think there is enough there to be a springboard for someone else - please read and decide for yourself!
Re:Slices of a datawarehouse? (Score:2, Informative)
The reason to do so in the first place is because the data's pattern or structure is way too complex for us to see (since it's only visible in high-dimensionality). Rather, we can calculate groups with linear algebra and then extract those groups and make a visualization out of them.
This is roughly hos Google operates; using LSI or LSA (in conjunction with ranking system and lots of other neat stuff).
The following is a great page explaining much of modern search engines and LSI and LSA -- finding patterns in highly complex data (including building a matrix for indexing of text):
http://javelina.cet.middlebury.edu/lsa/out/cover_