A graph is used to represent the social media networks, which are heterogeneous and multi relational. In social media networks, relationship between two entities are represented as links.
Characteristics of social network
The social networks are mostly dynamic and its graphical representation depends on the nodes and edges added or deleted over time.
Here are some characteristics of social media networks:
1. Densification power law:
In recent research, it is concluded that the networks become more dense over time with an average degree increase and so the number of edges grow linearly in the number of nodes.
Densification follows the growth power law as:
e(t) a n(t)a
Where,
e(t) and
n(t) are the number of edges and number of nodes at times t.
In this law, value of 'a' lies between 1 and 2; where a = 1 denotes the constant average degree of graph, while a = 2 denotes that the graph is extremely dense.
2. Shrinking diameter:
As the network grows, the effective diameter goes on decreasing.
3. Heavy tailed out-degree and in-degree distribution:
The number of out-degrees for a node is a heavy-tailed distribution and follows the power law as:
1/na
where,
'n' is the rank of node in sequence of decreasing out-degree and OCAC2.
The 'in-degrees' follow a heavy-tailed distribution though it seems to be more skewed than the 'out-degrees' distribution.
Social network Generation
- The forest-fire model is used in social network generation. This model is based on the condition that new nodes are attached to the network by burning through the existing edges in an epidemic fashion.
- This model uses two parameters, the forward burning probability 'p' and backward burning ratio 'r'.
For example: Consider a new node v, which arrives at time 't' and attached to graph 'Gt'.
Constructing graph 'Gt'
Step1: Initially, graph 'Gt' selects a node 'x' in a random fashion as an ambassador node and then creates a link with it.
Step2: The 'y' links, which are incident to 'x' links, are selected. Assume 'y' as a random number which is supposed to be distributed with mean (1-p)-1. Further, select the in-links in such a way that their probability of 'r' times is lower than out-links. This generates the nodes x1,x2,....xy at the another end of the selected edges.
Step3: New node v, generates the out-links to x1,x2....xy. Apply step2 recursively to each x1,x2...xy. Visit the nodes only once so as to prevent the cycle formation.
