Complex Network Metrology

In order to study some complex networks like the Internet, the Web, social networks or biological networks, one first has to explore them. So this blog gives a partial and biased view of the real object, which is generally assumed to be representative of the whole. 

Using the example of the Internet and a rough model of its exploration process, we show that the way a given complex network is explored may strongly influence the observed properties. We therefore insist on the necessity of developing a theory of complex network metrology. Its aim would be to study how the partial and biased view of a network relates to the properties of the whole network. Our global approach is the following: we consider a (known) network G, we simulate an exploration of this network to obtain a view G’ of it, and then we compare the two objects. The final aim is to deduce properties of G from properties of G’’. 

Modelling

We want to simulate an exploration process. In order to do this, we first need a network to explore. There are several natural choices for this. We will choose the most simple and well known model of random networks to generate the topology to explore: the Erdös and Rényi random graph model. This model has two parameters: the number of nodes, n, and the probability of existence of any link, p. A network is then generated by considering that each possible pair of nodes is linked with probability p. 

This gives an expected number of links m = p .n.(n-1)/2. 

The traceroute tool gives the path followed by messages from a source to a destination. Up to now, very little is known on the properties of such paths. For instance, one may suppose that the aim of network protocols is to deliver information efficiently, and so that the paths they follow are shortest paths (paths of minimal length). It is however known that this is not always the case, but no precise information is currently available on how they differ from shortest paths. Moreover, there exist in general many shortest paths for a given pair of computers, and there is no apriori reason for traceroute to give one of them rather than another. Finally, the paths change during time but again very few is known on their dynamics.In the current state of our knowledge, designing a realistic model of traceroute is therefore impossible. The assumption usually made is that traceroute always gives a shortest path, which will actually be sufficient for our current aim. We will also consider that, during the exploration process, one may use traceroute many times, which lead to the discovery of all the shortest paths between given sources and destinations.We have a model to generate the network to explore, and some models for the traceroute tool. We now need a model for the exploration process itself. As already noticed, we will suppose that it only relies on traceroute. But this is not sufficient: we must say how we will choose sources and destinations, and how many of them we will consider. Our aim being to show that the exploration method may influence the obtained view of the actual network, we will consider several realistic models of the exploration.

All the values we plot are averaged over 1000 instances. The variance is in general negligible (we plotted it in the case of Figure 2). The shortest path computations are done using breadth first search.

Unique source

Let us denote by Gu(x) the view of G obtained from a given source if we consider x random destinations, with the usp model for traceroute. Let nu(x) be the number of nodes of this view, and mu(x) its number of links. Similarly, we introduce Ga(x), na(x) and ma(x) the results obtained with the asp model for traceroute. The plots of these functions, Figure 1, show how much of the network we obtain, both in terms of nodes and links, as a function of the number of destinations. At various points, these plots fit well the intuition. First, when we consider very few destinations, we obtain a very small part of the network. Then, if the number of destination grows, we see more and more. Finally, we of course see all the nodes when we consider each of them as a destination.

There are however a few remarkable facts. Both nu(x) and na(x) grow rapidly and reach a critical point where they start a linear growth, but the initial growth of na(x) is much more rapid than the one of nu(x). On the contrary, mu(x) and ma(x) grows linearly from the beginning, but the maximal values they reach, mu(n) and ma(n), remain surprisingly low. It means that the exploration misses many links, even if we consider all

the possible destinations, which indicates that the obtained view is very incomplete. This is even more surprising when we consider the optimistic case where all the shortest paths are discovered, and all the nodes are used as destinations.

These behaviors are similar for any values of n and p (the plots presented in Figure 1 always have the same shape). However, the maximal value reached by mu(x) and ma(x), i.e. the maximal proportion of discovered links, varies with the probability p of existence of any link. To know how p influences these values, let us study the proportion of links discovered using one source and all the possible destinations, as a function of p. They are plotted in Figure 2 for the two models of traceroute we consider.

The two plots have some properties in common which can be easily explained. First notice that below a certain value of p, the network is not connected (it is composed of many independent parts). Therefore, below this threshold, any exploration using a small number of sources will give a very small part of the whole. When the network becomes connected, it is almost a tree, in which there is a unique path from the source

to each node. Therefore, the two exploration methods we consider discover almost all the links, which corresponds to the maximal values reached by the plots in Figure 2. On the opposite, when p is almost 1, then almost every possible link exists, and so almost every node is at distance 1 from the source. Therefore, the obtained view, both with the usp and with the asp model, is almost a star. It therefore contains almost 

n -1 links, which, compared to the total number of links, almost n·(n−1)/2 , is negligible. The plot for the usp model is easy to understand. Indeed, the exploration using this model gives a tree (it has no cycle), and therefore it contains exactly n - 1 links if p is above log(n)/n. 

Since, in this case the network is almost surely connected. The expected total number of links being itself 

m = p ·n·(n−1)/2 , the ratio between the number of links discovered during the exploration and the total number of links is then n – 1 / m = 2 / p · n. When p grows, this ratio decays as 1/p, which is confirmed by the simulation. On the contrary, the irregular shape of the plot for the asp model is very surprising: it has many peaks and valleys of high amplitude, which have no obvious interpretation.

This is so surprising that we will name it the camel plot. There is however a natural explanation of this shape, which comes from specific properties of the exploration.

 Several sources

Until now, we have restricted ourselves to explorations using only one source. However, in practical cases, one generally uses several, but few, sources. We investigate here how this may influence the quality of the view we obtain. Again, we only concentrate on the ratio of the total number of discovered links, which previous remarks have shown to be essential.

Figure 4 shows the evolution of this ratio when the number of sources is increasing. Let us first consider the two topmost plots, which correspond to the cases where we use all the possible destinations. As expected, the quality of the view grows rapidly with the number of sources, and one may even be surprised by the rapidity of this growth. Despite our model of Internet exploration is very rough; one may consider this plot as good news since it indicates that one does not need many sources to obtain accurate views of the network. This is important since it is very difficult (and never done) to use many sources in practice.

Conclusion

In this communication, we considered the simplest possible question concerning the quality of a network view obtained by an exploration of a real network: the amount of the total number of nodes and links we obtain. Making natural variations on the way we model the Internet exploration, we show that this amount varies a lot and is very difficult to estimate.

References

• R. Albert and A.-L. Barab´asi. Emergence of scaling in random networks. Science, 286:509–

512, 1999.

• R. Albert and A.-L. Barab´asi. Statistical mechanics of complex networks. Reviews of

Modern Physics 74, 47, 2002.

• R. Albert, H. Jeong, and A.-L. Barab´asi. Diameter of the world wide web. Nature, 401:130–

131, 1999.

•  R. Albert, H. Jeong, and A.-L. Barab´asi. Error and attack tolerance in complex networks.

Nature, 406:378–382, 2000.

Complex Graph Visualizations

(Please note that most images which follow are click-able hyperlinks.)

This post isn’t going to be about defining mathematical relations on complex graphs. It is about the first step - visualizing complex graph data. Of course, some people may like to differ about visualization being the first step but conventionally it is more or less assumed that visualizations play a major role in the initial study of complex systems’ data.

The most obvious question which comes to mind is “Why visualize?” since visualizations do not make any mathematical contributions to the data (not directly of course) nor do they augment the already existing data in any form. Here are some points which may answer this question.

• Visualizations help in identifying the major nodes (or the key players) in the graph being analyzed. We can “look” at which node is most influential, which node can disrupt the graph setting or which node's movement can alter major properties of the graph.
• Graph visualizations are also helpful in ascertaining various relationships between nodes. Say for example, if you have close to 800 facebook friends and about 10 are really close to you. You may want to invite the close ones to your birthday party and make sure that none of the invitees get bored due to lack of  presence of common friends at the party.
• Relationship strengths can also be determined from graph visualizations. The best example to quote here would be “The Hubway Data Visualization Challenge”.  Hubway is a bicycle sharing system in Boston, MA and is an absolute delight for visitors who wish to move around the city without having to keep track of the metro. The following visualization denotes the strength of relationship between each pair of stations. 

  
  
  
  
  
• Temporal analysis of complex networks is another crucial application of graph visualizations. Relationships and properties of a graph may change over time.
  
  
  Here is a visualization I made for half a million geo-tagged tweets collected during the Masters Golf Tournament 2012. The frames go a bit too fast because we did not want to exceed the time limit for our presentation. I recommend watching the 720p HD version of it in full screen mode.
• The identification of cliques or communities becomes much more apparent from visualizations and it is easier to compare the subgraph properties with the complete graph. Here is one of my favorites by Moritz Stefaner called well-formed eigenfactor. It gives an overview of a whole citation network.

  
  
  
  
  
  
• Graphs in 3D - Recently, I noticed some 3D visualizations of graphs. It felt like floating inside a web amongst the nodes. However, it should be admitted that 3D visualizations are not as helpful in extracting aggregated information but they are sexy! They might prove beneficial in enticing investors to your project.

This section of my post will enumerate some of the widely used tools for visualizing complex systems.

• Gephi is the photoshop for graphs. One can easily color, cluster and manipulate elements of the graph. It is open source.
• Sigma.js is a javascript library which brings Gephi on the web. It is also open source and has most of the layout algorithms as on Gephi with features like zoom in - zoom out, several ways to import and export data etc.
• Processing is the software for visual art. It was built upon Java and is one of the most sophisticated visualization tools present. The project was initiated in 2001 by the MIT Media Lab. One of its phenomenal applications were in visualizing graphs for Max Planck Research Networks project. The visualizations of the graph were controlled with fingers on a surface table. 

  
  
Processing also has many sister projects such as Processing.js for integration with the web and iProcessing for the iOS environment.
• D3.js (Data Driven Documents) is a JavaScript library for data visualization and is an important tool to generate interactive graphics from data. It was developed as a successor to Protovis by Prof. Jeffrey Heer and his PhD students at Stanford. Even if one is working with noSQL or graph databases, the end result of a query is always a table. Such resultant tables can be easily converted to json format on the fly for visualization with D3. The force-directed and force-collapsible layouts are very useful in visualizing weighted complex graphs.
• Cinder is the tool for you if you are a C++ fan. Even though Cinder may not be the first choice for most interaction designers, it may be the tool for you if you need the speed gain associated with C++ and you are ready to spend some time building stuff. It is also known as the toolbox for creative coding and is often the subject of blog posts trying to explain music generation and visualization.
• Flare, three.js, VivaGraph.js etc. are other such libraries for graph visualizations. VivaGraph.js is known to scale well for larger graphs.

References:
https://sites.google.com/site/steveborgatti/home
http://jonathanstray.com/visualizing-communities
http://max-planck-research-networks.net/
http://hubwaydatachallenge.org/
http://der-mo.net/
All other references are present in the form of hyperlinks above.

Small World Relationships

Hello everyone,

SUBJECT:

This posts looks at the correlation between geography and human relationships(friendship) and discusses applications of the same. 

BEFORE WEB BASED SOCIAL NETWORKS:

Before social networks emerged, human relationships were constrained by many factors requiring time, energy and often money to maintain. The likelihood of maintaining friendships fell off as geographical distance between the respective friends increased. A non trivial observation is that the total number of friends decrease with increasing distance from the concerned individual even though the total number of people are increasing. In other words, the probability of knowing a person x miles away is decreasing faster than the total number of people x miles away is increasing[1]. These trends have been observed in studies conducted across colleges, new housing developments and projects for the elderly. 

SOCIAL NETWORKS AND DISRUPTION:

The emergence of social network has broken the geographical constraints imposed earlier on social relationships. It has become very cheap(if not free) to stay in touch with people we know and to establish new relationships. 

Data from social networks brings new dimensions to the study of human relationships with respect to geography. First of all, the data collected from social networks is mammoth, allowing us to conduct our study at a scale(populations of several countries) that was not possible earlier. The analysis of human relationships with respect to geographical distance on social networks will allow us to either:

1. Disrupt the established paradigm between relationship and distance.
2. To introduce unprecedented data to validate these theories at the level of the entire human population.

In contrast to popular belief that social networks have broken geographical barriers between people, studies on US LiveJournal users[2] and MySpace users[3] reaffirm that the likelihood of friendship is inversely proportional to geographical distance distance between the users. However, at extremely long distance, the likelihood of friendship is constant irrespective of variation in distance. 

APPLICATIONS:

1. Past studies have been concerned with measuring human relationships based on distances. A recent study conducted by Facebook[1], attempts to determine the location of a user based on the locations of his/her friends(i.e just the opposite of what was being done). The social network graph consists of approximately 3.5 million nodes and 30 million edges. Facebook's friendship based geo-location algorithm(85% accuracy) outperforms IP-based geo-location(59% accuracy). 
2. Propinquity and social structure are the keystones of research in small world routing.
3. Location based services

REFERENCES:

1. L. Backstrom, E. Sun and C. Marlow. Find Me If You Can: Improving Geographical Prediction with Social and Spatial Proximity
3. D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, 
4. and A. Tomkins. Geographic routing in social 
5. networks. Proceedings of the National Academy of S
6. ciences, 102(33):11623, 2005.
 
8. E. Gilbert, K. Karahalios, and C. Sandvig. The 
10. network in the garden: an empirical analysis of social 
12. media in rural life. In CHI '08: Proceeding of the 
14. twenty-sixth annual SIGCHI conference on Human 
16. factors in computing systems, pages 1603{1612, New
18. York, NY, USA, 2008. ACM.

Terrorist Networks - A look into the 9/11 tragedy

We have all been talking about social networks for quite some time now. Let us today look at a very interesting application of complex networks in real life, which could (and has) saved thousands of innocent lives. Well, I am talking about terrorist networks, and how complex networks can be used to foil their vicious intentions.

After the world went into shock due to the 9/11 attack, many internal information came into light. In early 2000, the CIA was informed of Nawaf Alhazmi and Khalid Almihdhar's links to al-Qaeda. They eventually became two of the 5 hijackers of American Airlines flight 77. When such an information comes out, the Intelligence uses their connections to uncover the entire network, rather than capturing the suspects immediately. I believe, the same was done in this case as well, but unfortunately, correct action was not taken in time.

Valdis Krebs studied the 9/11 hijacker network using publicly available information. While creating the network, Krebs faced three problems, which are inevitable in modelling any covert network:

1. Incompleteness - Information purposefully not given by the investigators
2. Fuzzy boundaries -  Difficulty in deciding whom to include and whom not to
3. Dynamics - Such networks are always changing

He did a lot of background research on each of the 19 hijackers and built a trust network among them using open source information. This network had the hijackers as the nodes and edges were between those who had spent time living or learning together. This graph, the shape of a serpent, had a long mean path length of 4.75, in a network of less than 20 nodes. The network that he got was quite sparse, with many hijackers on the same flight being more than 2 steps away from each other. This contradicts intuition, as a planned task requires team mates to be close to each other. This, however, confirms with the terrorists' strategy to minimize damage - to ensure safety of others in case one is caught. This was also described in Osama bin Laden's infamous video tape found in Afghanistan. In the transcript, bin Laden mentions - "Those who were trained to fly didn't know the others. One group of people did not know the other group".

Then, Krebs remodeled the graph by adding new edges among the nodes who attended meetings together. Such meetings are held to coordinate among distant points and discuss progress. After such meetings, the ties go dormant again till activity demands. He added six edges (meetings) to the graph and the mean path length dropped to 2.79. In another graph that also included immediate correspondences, Mohammed Atta, the ring leader of the conspiracy, was shown to have the maximum degree and closeness centrality, but not betweenness centrality.

Two important conclusions that Krebs drew out :

1. All 19 hijackers were within 2 steps of the two original suspects uncovered in 2000
2. Social network metrics reveal Mohammed Atta emerging as the local leader

The study also pointed that important links were concentrated around the pilots. They made the perfect "take-out" points, by having unique skills and connections.

Such study clearly shows the emerging importance of social network analysis on such terrorist networks. In fact, the arrest of Canadian terror cell in June 2006 and a plot to blow U.S. passenger planes crossing the Atlantic Ocean in August 2006 was foiled using techniques similar to those in network analysis. Questions were raised on the U.S. Intelligence on why they could not stop this catastrophe from happening. After all this was their job, isn't it? But it is not so easy dealing with a network that focuses on secrecy and stealth.

Such covert networks behave quite differently as compared to social networks. In social networks, strong ties reveal close clusters. This is not true in case of covert networks. Strong ties, that may have been formed in training camps, keep the cells interconnected, but these mostly remain dormant and make these ties appear as weak ties. These links become active only when absolutely necessary. As the target event approaches, the network activity increases - the flow increases across known links, new links are formed, the cash flow reverses, etc. When these activities seem similar to the known patterns closer to disaster, it is time "cut out the middleman".

References:
[1] Valdis E. Krebs. Mapping networks of terrorist cells.
[2] P. V. Fellman, R. Wright. Modelling Terrorist Networks.
[3] United States Department of Defense. 2001. Transcript of bin Laden Video Tape. December 13.
[4] Wikipedia

Image courtesy:
Valdis E. Krebs. Mapping networks of terrorist cells.

Influence maximization in a social network

    In this blog post, I will be discussing about influence maximization in social networks. So, first let us consider influence in networks. Let me take an example, suppose in a network the members can have two possible opinions and also it is assumed that we can bribe the members to support our opinion, so the question is which members will be more preferred to be bribed to cause maximum support in our favour. Here comes the concept of maximum influence using which members who have maximum influence on the whole network will be selected  to be bribed.

  Now, social network acts as a medium for spreading influence among its members. By the term influence means using opinions, ideas,etc. Main motives of influence spreading are primarily: Product marketing, innovation spreading. The basic steps for maximizing influence can be grouped in the following way:

a. Some basic models of influence for the network.

b. Obtaining data or influence between nodes known as inter-personal influence( f(S): influence of a set of nodes S).

c. Some algorithmic formulations to maximize the spreading of influence.

 Two basic models of influence:

    i. Linear Threshold Model.

    ii. Independent Cascade Model.

    

Linear Threshold Model: In Linear threshold model a node u is influenced by each neighbor w according to a weight b(u,w) such that sum[b(u,w)] <=1 for all neighbors w of u. The next steps for this model are:

  

i.   Each node chooses a threshold uniformly at random from the interval[0,1]. Let us denote this threshold by thres(u). This attribute thres(u) represents the fractions of  neighbors of u that has to be active for u to be active.

ii.  We start with an intial set of active nodes. And in next step it follows that the nodes that were active in the (i-1)th step remains active in the ith step and we activate all nodes u such that
sum[b(u,w)]  >= thres(u) for all active neighbors w of u.

     

    

Independent Cascade Model:  Here again we start with an initial set of active nodes and then it does the following steps:

  

i.   When node u becomes active in ith step, its inactive neighbors in the ith step get a chance to get active. There is a probability p(u,w) that the inactive node w will be active. Node w will be active in (i+1)th step only if the node u suceeds in ith step. The model runs until no more activations are possible.

  

  

Algorithm for influence maximization:

    a. Algorithm: Greedy Algorithm

    b. Performance: Slighly better than 63% due to (1-1/e) approximation.  

    

Approximation Algorithm for influence maximization: 

Domingos-Richardson optimization problem: The influence of a set of nodes A is  f(A) which is the expected number of active nodes at the end of the process where A is the initial active set of nodes. The influence maximization problem is defined as follows:

     Given a paramter k, find a k-node set of maximum influence. For the two influence models described above, it is NP-hard to determine the optimum for influence maximization.

     One solution is that influence maimization can be approximated within a factor of (1- 1/e) in both the models, where e is base of natural logarithm. This performance gurantees slighly better than 63%. This performance is obtained by a greedy hill-climbing strategy. The steps of the greedy algorithm are as follows:

     i. We start with an empty set S.

     ii. While no more activations possible

       Add node v to S that maximizes f(S+v)- f(S)

     

     This greedy algorithm has (1-1/e) approximation. Its time complexity is O(kmns) where m is the number of edges, n is the number of nodes, and s is the number of times the model is simulated.

References:

1. D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD 2003. 

2. W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD 2009.

Computing Communities in Large Networks Using Random Walks

 In this blog we will discuss the computation of dense sub-graph (community) of sparse graph, which is very common in our real life complex network. We will give introduction about different way of computing sub-graph and finally will spread some light on random walk approach.

       Complex network has become important in different domain such as sociology (acquaintance or collaboration networks), biology (metabolic networks, gene networks) or computer science (Internet topology, Web graph, P2P networks). The Graphs of these networks are general globally sparse but locally dense. There exist group of vertices which are highly connected among itself, called communities, but few links to other. This type of structure carries much information about network. One real life example could be our Facebook friends if we draw our friends as node and link between them if they are friend among themselves then we will find a sparse graph having different dense sub graph(community) based on college friend , High school friend , School friend, colleague etc.

       Community Computation problem can be related to graph partition problem [1]in which given a graph G = (V,E) with V vertices and E edges, k-way partition of graph is partitioning of graph in k part such that number of edges running over these partitions are minimum. However the algorithm for Graph partition is not well suited for our case, because no of communities and their size is input for Community Computation.

     Hierarchical clustering is another classical approach in which nodes are grouped together based on the similarity between nodes, Newman proposed [2] a greedy algorithm that starts with n communities corresponding to the vertices and merges communities in order to optimize a function called modularity which measures the quality of a partition.

  

       The approach which is discussed here is based on the random walks on a graph [3] tend to get “trapped” into densely connected parts corresponding to communities. The graph G has its adjacency matrix A: A_ij  = 1 if vertex i and j are connected and A_ij   = 0 otherwise. The degree d(i)   of the vertex i is the number of its neighbors. A discrete random walk is a process in which a walker is on a vertex and moves to vertex chosen randomly and uniformly among its neighbors. The sequence of visited vertices is a Mrakov chain, the states of which are the vertices of the graph. At each step, the transition probability from vertex i to vertex j is P_ij    =A_ij/d(i). This defines the transition matrix P of random walk. The probability of going from i to j through a random walk of length t is (P^t)_ij. It satisfies following two properties of random walk.

Property 1:  When length of a path between two vertices i and j tends toward infinity. The probability that a random walker will be at vertex j will totally depend on the degree of vertex j

                                        

Property 2: The ratio of probabilities of going from i to j and j to i through a random walk of a fixed length t depend on the degrees d(i) and d(j).

          

    For grouping vertices into communities, we will now introduce a distance r between the vertices that captures the community structure of the graph. This distance will be large if two vertices are in different communities, and on contrary if the distance is small they will be in same community. It will be computed from the information given by the random walk of the graph.

    Let us consider a random walk of length t from vertex i to j . t is large enough to gather the topology of graph. However t must not be too long to avoid property 1. The probability P^t_ij  would depend on the degree of the vertices i and j. Each P^t_ij gives some information about the two vertices i and j, but property 2 says that P^t_ij and P^t_ji encode the same information. Finally the information about vertex i is encode inside n probabilities P^t_ik  1<k<n. Which is nothing but the i^th row of matrix P^t. For comparing two vertices we must notice following points.

·         If two vertices i and j are in the same community, the probability P^t_ij  will be high be high but if P^t_ij is high it does not necessarily imply that i and j will be in same community.

·          High degree vertex will have always high probability that a random walker will reach there. So P^t_ij  is influenced by the degree d(j) of vetex.

·         Two vertices of a same community observe all the other vertices in same way. Thus if  i and j are in same community then

                                                      

References

[1]Graph Partition Problem

     http://en.wikipedia.org/wiki/Graph_partition

[2]Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Physical Review E 69 (2004) 066133

[3]Computing Communities in Large Networks Using Random Walks - Pascal Pons and Matthieu Latapy 

Complex Contagion in Complex Network

     Following up on the previous post referring to rumor spreading in social networks, I would like to extend the topic to complex contagion in a complex network.

     This phenomenon tells us you will take some action or adopt a changed behavior only if certain fraction of your friends do so. This is different from spread of diseases or rumors. Complex contagion examples include whether to join a protest, see a movie, adopt a new hairstyle or get a tattoo.

     Damon Centola of Harvard University and Michael Macy of Cornell University suggests four properties that necessitates multiple exposure , namely strategic complementarity, legitimacy, credibility and emotional contagion. I'll fall back on a very recent experience of mine when the movie 'Django unchained' was released ( or when its blu-ray print became available?). One of my friends (the movie nerd?) told me it was a good one, then another couple of friends supported him. Within a week, six of my friends watched and recommended it. If this happens to you, I am sure you'll also utter the already famous quote from the movie :
"You had my curiosity but now you have my attention." and go and watch it (I am sorry, I couldn't resist).

Mathematical Model

    The diffusion through all of the network or cascading effect as indicated above can be explained through a very simple mathematical model.

• Whether or not you'll adopt a behavior or choose one of two possible alternatives depends upon a payoff . 
• It also depends upon the fraction of your friends/neighbors who have already chosen one.

    Suppose, p fraction of your friends play cricket and other (1-p) fraction play football. The payoff (i.e. your willingness) for playing cricket is c and playing football is f.

Now, you would choose cricket over football if,  

                                                                         p.c > (1-p).f

In other words, p > f/(c+f).

    So in the network, if q fraction of your neighbors play cricket where, q > f/(c+f), you will also play cricket and in doing so, influence your other neighbors who play football to play cricket. In time, this results in the cascading effect.  

     

Complex Contagion : some interesting aspects    

• Long ties that connect socially distant relation, drastically bring down the degree of separation and results in fast information diffusion. So, a trend in fashion arising in anywhere in the world, should also readily affect India, right? After all, it's a small world. Unfortunately, the answer is no. Long ties not necessarily speed up the complex contagion process and may have no effect in this. Having many common neighbors helps in this process more. You are much more likely to join a protest if three of your close friends join it, in contrast to when your foreign friend whom you met during a holiday or intern joins it.
• Social networks have community structures embedded in it. Communities provide an interesting study. Within a community, there are many mutual links and an opinion spreads faster  and more easily,  encompassing the whole community. New opinions coming from outside the community share a different response. Links are sparse between different communities and different opinion of a different community is met with considerable resistance and a community is more likely to hold on to its own within group opinion even though it may be inferior compared to the new idea. This might tell you why parental 'community' finds teenagers' take on life 'rebellious' !!
• Moreover, when having two ideas, an individual can choose both for an additional cost. Falling back to our previous example of playing cricket and football, one (the sporty one!) may choose to play both with the additional cost of his or her own time. These 'bilingual' nodes help in coexistence of both kinds of opinion, here cricket and football and prevents one taking out the other one.
• While trying to spread an idea throughout the network, if one chooses the seed nodes carefully and inflicts them with the idea by whatever means (like a free cricket bat and ball for all those who will start to play cricket first), they may initiate the cascading effect. This has huge implication in viral marketing.

References            

• Wikipedia   
• Centola, Damon; Macy, Michael. "Complex Contagions and the Weakness of Long Ties."  
• Coursera : social network analysis, 2012                                                       

       

Theory of Rumor Spreading in Complex networks

Today in this blog we will deal with the world most beautiful and dangerous invention named as rumor. Rumors spreading play an important part in shaping of the world.  The spread of rumors can shape the public opinion in a country, greatly impact financial markets and also can cause panic in a society during wars. Thus one can possibly imagine the viral marketing of the rumor one’s it goes over internet or any social networking site. Most of the corporate world now uses WWW to spread rumor over Internet and “world-of-email”.

Rumor can be viewed as an “infection of mind”. Here we will primarily focus our discussion on Graph node rumor spreading by standard model of Daley and Kendal or the DK model and Maki-Thomson model. DK model divides the population into three major categories namely: Ignorant, Stiflers and Spreaders.  Rumors are spread via pair-wise contact of spreaders and others in the population.

S: People who are ignorant of the rumor;

I: People who actively spread the rumor;

R: People who have heard the rumor, but no longer are interested in spreading it.

Any spreader involved in a pair-wise meeting attempts to “infect” the other individual with the rumor. In the case this other individual is an ignorant, he or she becomes a spreader. In the other two cases, either one or both of those involved in the meeting learn that the rumor is known and decided not to tell the rumor anymore, thereby turning into stiflers.

In social networking let us consider the Graph G (V, E). Following Maki-Thomson model graph consider a population consisting of N individuals and rumor can only spread by direct contact along the links..

Whenever a spreader contacts an ignorant, the ignorant becomes a spreader at a rate λ .

When a spreader contacts another spreader or a stifler the initiating spreader becomes a stifler at a rate α

In the above, the first rule models the tendency of individuals to accept a rumor only with a certain probability which, loosely speaking, depends on the urgency or credibility of a rumor. The second rule, on the other hand, models the tendency of individuals to lose interest in spreading a rumor when they learn, through contacts with others, that the rumor has become stale news, or is false. In both the DK and the MK rumor models, and their variants, stifling is the only mechanism that results in cessation of rumor spreading.

We will describe above model using IMC framework (mean field equations). IMC was initially introduced to handle means for modeling social processes involving several agents. It consists of N nodes and internal transition is not only depended on the current node but also on the node adjacent to the  current node.

Consider now a node j which is in the ignorant state at time t. We denote with p_ii^j  the probability that this node stays in the ignorant state in the time interval[t +∆t ] and with p_is^j = 1- p_ii^j   the probability that it makes a transition to the spreader state. It then follows that

p_ii^j  =(1-∆t λ)^g ,

where g=g(t) denotes the number of neighbors of node j which are in the spreader state at time t.

The corresponding probability for a transition from the spreader to the stifler state, p_sr(k,t) is given by

p_sr(k,t)=1- p_ss(k,t).

The final size of the rumor, R is shown as a function of the spreading rate λ for the ER network of size 10⁶. The results are shown for several values of the stifling parameter α.
References:
[1] Theory of rumor spreading in complex networks. M.Nekovee, Y.Moreno, G.Binaconi, M.Marsili
[2] Rumor spreading in social network-Wikipidea, http://en.wikipedia.org/wiki/Rumor_spread_in_social_network

Academic Search Engine Optimization (ASEO)

In this blog we will take a look into Academic search engine optimization, how do Academic search engines (ASE) rank the documents (scholarly articles) and most importantly how can one optimize scholarly literature for academic search engines in general and for Google Scholar in particular.

The basic concept of keyword-based searching is the same for all of the major academic search engines such as Google Scholar, IEEE Xplore, PubMed, and SciPlore.org. Relevance of a document with respect to a query term depends on how many times the term appears in the document and where. This means that an occurrence in the title is weighed more heavily than an occurrence in the abstract, which carries more weight than an occurrence in a (sub)heading, which in turn is more than in the body, and so on.  The metadata associated with the electronic files (like in pdf format) is also important as it helps the ASE crawler to differentiate between an ordinary document and an academic article (by extracting the author and title from metadata). Apart from this other common ranking factors are: publication date, citation count, author or journal name and reputation etc.

 So how does Google scholar do it? Google Scholar is one of those search engines that combine several factors into one ranking algorithm. The most important factors are relevance, citation count, author name(s), and name of publication.

Relevance: Google scholar gives a lot of importance to the title and a short and specific title will be ranked above long and descriptive one. E.g.  For the search term ‘SEO,’ a document titled ‘SEO: An Overview’ would be ranked higher than one titled ‘Search Engine Optimization (SEO): A Literature Survey of the Current State of the Art.’ The total search term count has minimal effect on ranking, synonyms and pdf metadata are also neglected.

Citation Count: As shown in the figure below higher the citation counts higher the ranking. . Google Scholar does not differentiate between self-citations and citations by third parties.

Author and Publication name: If the search query has author or publication name then the documents having the name gets a high rank. Google scholar also claim to take both author’s and publication’s “reputation” into account.

     Every researcher wants to spread his/her work to as many people as possible. But for doing that it has become almost necessary to ensure that the article must not only be indexed properly but should also be ranked higher by Academic search engines; that’s where ASEO come into the picture. As described in a recent paper by Joeran Beel, Bela Gipp, and Erik Wilde, Academic search engine optimization (ASEO) is the creation, publication, and modification of scholarly literature in a way that makes it easier for academic search engines to both crawl it and index it.

Preparation: First of all build a set of keywords(only a few) which are highly relevant to the article. The choice of keywords is very important; they should not be the most popular in their category as it may increase the competition for the article. One can take help of tools like Google trends, Google insights etc. or can use the words suggested by search engines themselves.

Writing the article: while writing the article the keywords selected above must be used in title, abstract and in the body as often as possible (but not too much that will annoy the readers). If possible include synonyms of these keywords in the text as well, so that it may be found by users unaware of the exact terminology. While writing names, take special care on spellings as it would help search engines to identify the article or citations correctly. Use the standard scientific layout and structure for the article so that ASE could easily classify the article as scientific.    

Preparing for Publication: Text in figures and tables should be machine readable so that it can be easily indexed by ASE. If the documents are converted to pdf then the metadata (author and title name) should be correct.

Publishing: while publishing choice of publication matters a lot for e.g. open-access articles usually receive more citations than articles accessible only by purchase or subscription. Journals or publishers who have friendlier policies with Google scholar and other ASEs must be preferred.

            ASEO had received mixed reviews in the scientific community as many people look this area of research just as “how to cheat the search engines to boost up your rank”. That’s why when Joeran Beel, Bela Gipp sent their paper for review it got rejected and they received following reviews:

“I’m not a big fan of this area of research […]. I know it’s in the call for papers, but I think that’s a mistake.”

“[This] paper seems to encourage scientific paper authors to learn Google scholar’s ranking method and write papers accordingly to boost ranking [which is not] acceptable to scientific communities which are supposed to advocate true technical quality/impact instead of ranking”

But it should be viewed as guidelines which will help search engines to understand the articles in a better way thus making the content more widely and easily available. Obviously there would be cases where people will take unethical steps to boost their article rank using ASEO but the same problem existed with web search and finally the web search engines manage to avoid spam, thus ASEs will too catch up and it will be beneficial for authors and users alike.   

References

Joeran Beel, Bela Gipp, and Erik Wilde. Academic Search Engine Optimization (ASEO): Optimizing Scholarly Literature for Google Scholar and Co. Journal of Scholarly Publishing, 41 (2): 176–190, January 2010

Dog Programming Language

Developed by Sep Kamvar, Salman Ahmad and Zahan Malkani at MIT, this high-level Programming language, Dog, allegedly "makes it easy to create social applications by employing natural language commands.

The language emerged from Kamvar’s frustration with writing tonnes of code for defining social interactions in conventional languages like Java. He felt simple and intuitive interactions, say listening for someone’s facebook posts, had to be thought of in the realm of data storage and protocols. According to him these are better and more intuitively described using the natural language.

"I had to write code at a lower level of abstraction than I had to think about the interactions," he says. "And so I thought it would be interesting to start writing a programming language that allowed me to write at the same level of abstraction that I think."

And so he set out to create a new programming language, Dog (named such perhaps to convey the friendliness of the language, except to Cynophobes and cat people).Kamvar and his team of students have been developing the compiler for the language along with some demo programs. The public version of Dog is slated for release by summer this year. The language will be kept free and open source.

Dog identifies people as a basic data type, Kamvar believes that the major problem in defining social interaction using conventional languages is the notion of people. Following his approach of natural language, he created a syntax for the language utilizing simple words like listen, notify, ask, compute etc.

The promised product does indeed look much less intimidating than languages like Java. For example creating a group “students” can be simply done as: students = PEOPLE FROM facebook WHERE university = 'iit' AND degree = 'computer science'. Which resembles our ever so friendly Structured Query Language.

The use case of Dog is expected to be as follows, suppose you want to create a social application which requires standard computational tasks as well as a variety of social tasks say, listening to news feeds, messaging people, handle interaction events. Doing all this in a traditional language is a daunting task, especially the social aspects. By using Dog, you can abstract such things to simple code, which will be taken care of by Dog, while other programming languages can still be used for the non-social aspects of the application.

  

According to the MIT media page, 

"Dog is a new programming language that makes it easy and intuitive to create social applications. Dog focuses on a unique and small set of features that allows it to achieve the power of a full-blown application development framework. One of Dog’s key features is built-in support for interacting with people. Dog provides a natural framework in which both people and computers can be given instructions and return results. It can perform a long-running computation while also displaying messages, requesting information, or even sending operations to particular individuals or groups. By switching between machine and human computation, developers can create powerful workflows and model complex social processes without worrying about low-level technical details."

As of now, the language is for server side applications, but the team is also developing similar mechanisms for the client side.

Kamvar believes that Dog will enable non-programmers such as interaction designers or product managers to easily understand what the website is doing and what all functions are being used internally.

Salient features of the language

• Identifies people using SQL query like commands, like
  good_students = PEOPLE FROM iit WHERE gpa < 9
• Makes communication tasks, like sending messages, emails, listening to posts easier,
  LISTEN TO students VIA email FOR assignments
• Supports integration with other languages, such as imports from Python
• Simplifies asynchronous state management,
  LISTEN TO users FOR tickets
  ON ticket DO

Will this be a game changer for the social application developers? We cannot say.
Would it help students enrolled in the Complex Networks course with their projects? Not with these timelines it won’t.
But what it does do, is bring up this interesting debate of whether Programming languages are indeed unnecessarily hard and more work could be put into them, to make them more accessible.

Links

www.dog-lang.org

http://www.media.mit.edu/video/attachments/2012-04-25/sdkanvar-2012-04-25.pdf