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."
Slices of a datawarehouse? (Score:4, Insightful)
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.
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
Studing the internet as a social network (Score:4, Funny)
Re:Studing the internet as a social network (Score:2)
Slashdot?..... (Score:5, Insightful)
I have often wondered this about Slashdot itself. It would appear to me that Slashdot would provide an ideal means to mine data on complex interactions that may have implications for anything from database design to network load analysis or perhaps the results may even apply to the modeling of biological systems. The owners of Slashdot would be missing something big if they were not examining Slashdot very carefully.
Mapping the Internet only has so many applications, but if one really wanted to make an obscene amount of money, figuring out how to model systems is where it would be.
Re:Slashdot?..... (Score:4, Funny)
If only they would read some of the comments and realize that the answer is 42, they might be able to work faster backwards from the answer.
Re:Slashdot?..... (Score:5, Interesting)
I'd be more interested in seeing the data that gets deleted, not the clumps. This isn't to say that the clumps aren't important, especially if you're trying to rebuild oyster populations in the Chesepeake or some such, but plenty of people will be focusing on those. People have an attraction to like objects and group mechanism.
I have an attraction to the exceptions. That's where the really interesting scientific stuff is likely to be happening, and where the Nobels are most likely to be hiding.
Why is this star off the main sequence? How did it get there, what makes it tick? What relevance might that have to stars that are on the main sequence?
KFG
Re:Slashdot?..... (Score:5, Interesting)
Following data clumping, it's really the interactions or the nexus of contact that is interesting. For instance, from a computer science or informational processing perspective, what draws someone to a piece of information? How does one direct information to be most useful? In biological systems, the nexus points are where life happens. For instance, the small molecular fluxes that are constantly providing for molecular signaling, protein synthesis etc.... Information is not lost per se, rather there are information fluxes.
So, to answer your question of stars, it could simply be that a particular star is off the main sequence because of earlier smaller phenomenon that resulted in its appearance much later off the main sequence. Alterations in gravity? Interactions with a binary star? Alterations of proton-proton chains?
Re:Slashdot?..... (Score:3, Interesting)
In the biological field we may discover Black Smokers, where we learn more about life in general than we do when studying oysters and their ecologies.
It's simply my preference to overtly assume something like Black Smokers are out there somewhere and go looking for them.
In social networks you'll often find
Re:Slashdot?..... (Score:2)
Re:Slashdot?..... (Score:2)
What it doesn't say: (Score:2, Funny)
Re:What it doesn't say: (Score:1, Funny)
Re:What it doesn't say: (Score:4, Funny)
Searching usefulness? (Score:5, Funny)
Re:Searching usefulness? (Score:3, Funny)
So that's like, what, pictures of dressed people?
Re:Searching usefulness? (Score:2)
And lots of pictures of people not having sex.
Or is that not lots of pictures of people having sex?
ObStoppard:
"I've frequently not been on boats."
"No, no, no - what you've been is not on boats."
Re:Searching usefulness? (Score:2)
"I shall not today attempt further to define the kinds of material with a rigorous boolean expression, but I know it when I see it."
oh my.. the high-school friend one.. (Score:5, Interesting)
http://www-personal.umich.edu/~mejn/netw
The little single dots on the left..
you have to feel bad for them..
and all the "fringe" people.. they are visibly shown on the fringe..
kind of interesting..
Re:oh my.. the high-school friend one.. (Score:5, Funny)
Re:oh my.. the high-school friend one.. (Score:1)
Um... no, it's not. It's pretty clearly labeled [google.com] as a graph of high school friendships.
Re:oh my.. the high-school friend one.. (Score:5, Funny)
Check out that stud on the left who is banging like 8 different girls.
nine (Score:2)
Spot the Bis! (Score:2)
Also, like a dirty Where's Waldo, can you spot the bis? I can see six. (Only two of whom, I might add, enjoy a stereotypically large number of partners.)
Aside: what would the explanation for the big cycle be in social terms? I see only three other cycles, but two of them are caused by frat spirit so they don't count.
Re:Spot the Bis! (Score:2)
I was wondering the same thing. The only explanation I could come up with was alphabetical ordering.
IIRC there was once a study of graduates from a police academy where rooms were allocated alphabetically. Years after they graduated, there was a strong correlation between two graduates' alphabetical proximity and the likelihood that they had remained friends. Conclusion: you can learn to like almost anyone if you're forced to spend time tog
Re:oh my.. the high-school friend one.. (Score:2)
And look! This will take you back to your first year CS class (and if you were in CS class, you weren't getting any, either): the researchers have discovered recursion (emphasis mine):
Re:oh my.. the high-school friend one.. (Score:2)
Unless, and that's the kicker offcourse, the disease first came into existence in this person, by mutating form some other harmless variant or something.
Re:oh my.. the high-school friend one.. (Score:2)
Many human diseases -- influenza, some plagues, and many STDs -- originated in animals, and mutated enough to cross the species barrier.
In the case of STDs, it seems a fair guess that some lonely shepherds, uh, "encouraged" teh crossing by crossing -- or breaking -- a few moral and membranous barriers on their own.
Re:oh my.. the high-school friend one.. (Score:1)
Re:oh my.. the high-school friend one.. (Score:2)
Re:oh my.. the high-school friend one.. (Score:3, Interesting)
Those dots are lonely.
Re:oh my.. the high-school friend one.. (Score:2)
I don't know what's sadder, the people with one arrow in and none out, one out and none in, or none at all.
Pattern Depth -- does chaos exist? (Score:5, Interesting)
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/
orkut: pricacy, data protection, terms of service (Score:1, Offtopic)
I heard of account deletion because of faked/spoofed "delete my account" mails.
Remember to check their Terms [orkut.com] :
By submitting, posting or displaying any Materials on or through the orkut.com service, you automatically grant to us a worldwide, non-exclusive, sublicenseable, transferable, royalty-free, perpetual, irrevocable right to copy, distribute, create derivative works of, publicly perform and display such Materials.
They invented their own licencse. What do you think if Micro [guardian.co.uk]
Social Networks are diluted (Score:3, Insightful)
There should be some kind of requirements forcing you to somewhat communicate with these people, otherwise they should be off your list.
These social networks are giving "friends" a real bad definition.
Re:Social Networks are diluted (Score:5, Interesting)
One aspect of the problem is the granularity by which relationships are defined. In many of the sites there is only one state: "friend or non friend". The real world encompases a number of shades and types, from business acquaintance to personal friend, intimate lover, etc.
Another aspect is the incentive to "game" these systems by increasing your friend count. This inevitably leads people loosening their interpretation such that they increase their visibile friend count. If the number if friends you were linked to was not public, there would be less of this (but you can't do that without breaking some of the functionality of the sites)
People have talked about "winning" at friendster or tribe or orkut - but there is no "winning" in these systems, as there should not be competition.
Last, there is no method for verification of any status between peers. Can you "prove" that so and so is really a friend?
There are others, but these are the main three, and not likely to be solved or addressed any time soon.
Re:Social Networks are diluted (Score:2, Interesting)
freindship (Score:2, Informative)
Re:Social Networks are diluted (Score:2)
I certainly hope I can call a few of them to go out when/if I visit that State...
Re:Social Networks are diluted (Score:2)
incentive to "game" these systems by increasing your friend count.
This phenomena is not something new to online communities.
Politicians and salesmen have tried to "game" social networks for millenia.
And if you really want to study some interesting social networks, consider Multi Level Marketing (MLM) schemes which are often replete with zealous, almost religious fervor about Success and rely upon social networks for growth and an occassional well-placed meme, such as "Women Gifting Women".
Where it w
Re:Social Networks are diluted (Score:5, Interesting)
Granted, its a set of small steps towards understanding the opposing point of view, but it does help broaden my horizons.
It's actually a very useful system.
High school dating chart (Score:5, Funny)
Re:High school dating chart (Score:2, Funny)
Re:High school dating chart (Score:1, Funny)
Re:High school dating chart (Score:3, Insightful)
Re:High school dating chart (Score:1)
Seems pretty clear to me...
Re:High school dating chart (Score:2)
If we presume that pink are girls and blue are boys, there is one poor dude to the right of that guy that looks like he took 3 of the others castoffs.
I see only 1 homosexual relationship in the upper left corner, despite the chestnut that upwards of 10% of high school students are gay.
It would be interesting to plot this 3-dimensionally, to set them in a z-axis chronologically, and/or weight the connections for the duration of the relationship.
Interesting but hardly new (Score:4, Informative)
Re:Interesting but hardly new (Score:2)
Newman, Watts, Barabasi and others are trying to understand the nature of these types of networks (and other types), rather than just the content of the networks (orkut, slas
denominator (Score:4, Interesting)
The denominator in these equations should be the peer pressure quotient: the desire of most people to be like most other people.
Finally, something useful (Score:5, Funny)
Finally, something that can help me understand the divisions in the NHL. I've been confused ever since they got rid of Smythe, Norris, and all the rest...
Astounding social implications. (Score:5, Interesting)
Imagine a system which tells you, easily enough, who the 'most popular person for subject ___Y___' is, in your neighborhood? Target a campaign of computer-buying to only -3- folks in an area, and end up blanketing the entire region with tuber-like memes...
PR agencies could use this data to identify the core 'gossip leaders', the ones who have massive impact on multiple peers, and then they could target only those people with their campaigns
There are numerous religious theories, also, on the strengths of individuals and groups and the effect that these social connections have on a movement
This is the danger zone. The moment we start using computers to do qualitative analysis of social dynamics, and then using the data for commercial/religious/nefarious purposes, well
Re:Astounding social implications. (Score:3, Funny)
Could? (Score:2)
And we are already in the danger zone, you really think the big advertisers have been ignoring this kind of thing?
Re:Could? (Score:2)
1. Pick a random kid at a school.
2. Ask them who the coolest person is that they know.
3. Go to that kid and repeat the process.
4. When you find a kid who responds that they are the coolest person they know, you've found your trend leader.
Give them a toy/CD/etc. for free, and you've seeded your viral marketing campaign.
Re:Astounding social implications. (Score:2)
Re:Who says it's bad? (Score:2)
Phone Book Network (Score:5, Interesting)
We have 7-digit phone numbers and two mobile networks here in Latvia. Data can be stored this way:
6787026 -> 9131415
9131415 -> 5956564
etc...
All we need is one hashtable (or MySQL table) and data collection interface
Re:Phone Book Network (Score:3, Interesting)
Wow (Score:3, Funny)
Re:Wow (Score:2)
n degrees of separation (Score:4, Funny)
Then again, most people will probably have a connection to Nigeria due to the certain organ-lengthening drug that they are so famous for.
Re:n degrees of separation (Score:3, Funny)
I have heard about it too. In fact, there are two persons between me and Vladimir Putin or Bill Clinton, and only three persons between me and Monica Levinsky...
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.
Profound and meaningless (Score:5, Insightful)
A quick reading on Zipf's Law [google.com] shows that many natural systems (and many artificial ones that obey similar laws of construction and equilibrium) observe 'power rules' where the distribution of power is inverse to the number of entities at any level.
Surprising that earthquakes, cities, businesses, follow the same rules. And yet quite meaningless in any direct sense because we can't manipulate these rules, only observe them.
Human social networks also follow rules that I suspect are quite simple and possibly similar to Zipf's Law. For instance, a person can only maintain a finite number of contacts (technology may increase this number but it remains finite at any given time). Any new contact coming in displaces an existing contact. So a single person's contact list will follow a power law: twice as many contacts used half as often, ten times as many contacts used a tenth as often...
Mapping a contact network would need to take the importance of each contact into account. I may have my grandmother in my list, but I speak to her once a year. My accountant - every week. My wife - twice a day. My girlfriend - every hour.
Next: the differences between individuals in terms of how much time/skill they invest in networking. Gender differences... women do this much more and better than men, in general. Age differences... younger men do it less well than older men. Wealth differences... richer people do more networking, I'd suspect, until a certain point when they start to delegate it. Very poor people do very little networking.
So, the network is not a flat map. It's got two dimensions for the lines, but each line has a thickness, and each node (individual) has a size.
Finally, I'd suspect that the network also maps power in terms of social success. Those people with the most powerful networks (a recursive definition: the networks which involve the most powerful people) will also be the most successful socially / financially.
But they may not be the happiest.
Role-Based Relationship Weights (Score:5, Interesting)
Rather, the network needs some form of role-based assertion or qualification of the relationship. I know friends that I like to go hiking with, but that I disagree with politically. I know people that I do trust to recommend software, but don't trust to recommend a restaurant. And if I trust person B to recommend software, I would probably only trust that person B to recommend another person C in a limited set of domains (like software or technical issues). Thus the real relationship is more like person-A-trusts-person-B-for-role-C.
Such a scheme of role-defined relationships could be self-organizing or predefined. The self-organizing approach would look for disjoint clusters of members in a network or use semantic analysis of the messages passed between people to infer a set of role-clusters. Predefined relationship might be OK, but could become unwieldly if the network creators force people to answer a long multiple-choice test about every relationship.
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
Re:Role-Based Relationship Weights (Score:2)
Hmm... (Score:5, Insightful)
Re:Hmm... (Score:2)
Crackers and malicious companies are, frankly, the very least of your worries. Bush and Ashcroft are already busily data mining commercial databases, airline records and the rest. They do this because they cannot gather much of this information themselves either for financial legal technical or political reasons.
But Orkut Friendster et. al. even if they havent alrea
Re:Hmm... (Score:2)
seriously. the social networking efforts are going to be no worse than people's subscription to magazines and owning a credit card.
what is actually disturbing, here in reality, is the privacy policies that each company declares on their site. Yes, Orkut has an INSANE privacy policy, but Tribe, Friendster and some smaller others look like they mean to make priva
Football? Friends? (Score:3, Funny)
Oh, there it is, "..to food webs".
Highschool Friendships (Score:5, Funny)
Check out the "highschool friendships [umich.edu]" diagram.
I think I was the yellow dot on the far left.
Re:Highschool Friendships (Score:2)
There were many of us like that.
Mapping weblog communities (Score:5, Interesting)
Conceptual Clumps (Score:5, Interesting)
Similar in the way that grokker clumps navigable areas together, it would be interesting to instead clump things together based on the relations of the meaning of the information they contain.
For example, lets say that you are reading an article on any given site. You would be able to highlight a phrase, a word or a sentance, then look that term up in context. This is different than simply googling the term in that you are looking for the context of the term as opposed to a concrete definition.
so if you were reading an article regarding the legal take over of a company by intel, you would be able to easily search for articles writen that involve intel in any other litigation, with results containing intel involved in purchases or sales of companies and their technologies coming to the top of the list...
obviously there is a lot more in this required to accomplish it - so Ill just stop here before giving it all away.
The main point being that this type of searching is easily applicable to understanding relationships in social networks as far as identifying how common intrests are shared.
The clustering of attractions and dislikes to profile trends and personalities in any given demographic are made especially easy in systems such as friendster and orkut. By having people OPT-IN to the deepest marketing database available and provide you with all the details of not only the things they like (under the guise of sharing yourself with the others in the community) AND showing you what other people they are connected with who share common interests is one of the biggest social hijacks ever.
Just when you thought marketing was a dead science that is too transparent to have any real impact, social networks arise to provide marketing data on an astounding level.
[don tin foil hat]
Just wait till they are able to correlate all this info with DNA profiles
Not that this is bad per se, but it is a fact taht this info will be the next gold standard in market research where marketing will move to a social promotion system.
I think that the goal here is the promotion of product will largely come from people advertising their likes of a product through their profiles and communications with friends online.
It will be very easy for a group of people to communicate things (it already is) that are of interest to their social networks. Like on person telling the other 65,000 friends they have how they jsut experienced product Y, and that everyone should try it....
interstingly, will we see fakesters made specifically to spam the other friends with testimonial like adverts for products they are trying to introduce to a specific demographic?
Link to paper (Score:4, Informative)
Where's the beef? (Score:4, Interesting)
I've been singing the praises of LGL [utexas.edu] as of late, pushing it into the Opte project (mass internet viz) and such, but truly the interesting applications involve analysis -- and where's the beef on that in this story?
--Dan
Been There, Done That (Score:5, Funny)
My experience (Score:5, Funny)
... and the brain (Score:5, Interesting)
Re:... and the brain (Score:2)
Need Orkut Account (Score:1)
Thanks
At the University of Michigan... (Score:1, Interesting)
You are here (Score:4, Funny)
see social network maps online (Score:2, Informative)
Social dynamics in Open Source Groups (Score:1, Informative)
Six degrees (Score:4, Interesting)
How to train the networking software (Score:4, Interesting)
Basically, we have to find a way to "train" the software. It's not going to be easy. Training the TiVo still doesn't give you the best results. The personality compatibility tests sure are interesting, eh? Who here has been matched with the perfect roommate in college? Yet I haven't seen much yet on the weights of interests, just discussions about clusters of tight-knit social groups.
Introverster: the new way to get rid of people. (Score:2, Funny)
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 artifici
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:If you want the real scoop on social networks.. (Score:2)
Flight From Quality (Score:2)
Why use the scattershot TV ad to get us to buy a new car when they can simply allow the desirability of ownership trickle down the social food chain?
This is "Keeping up with the Joneses" taken to perfection. Once it is calculated which other individual or group we all choose to imitate, you find that there are only 30 people in the world who have to be given that new promotio
a view from the future (Score:3, Funny)
congratulations (Score:2)
Let's use this information... (Score:3, Funny)
Re:The only pattern I've noticed... (Score:3, Funny)