PROJECT TITLE :

Efficient Algorithms for the Identification of Top-k Structural Hole Spanners in Large Social Networks - 2017

ABSTRACT:

Recent studies show that people in a very social network will be divided into completely different groups of densely connected communities, and these people who bridge totally different communities, called structural hole spanners, have great potential to acquire resources/information from communities and thus benefit from the access. Structural hole spanners are crucial in several real applications like community detections, diffusion controls, viral selling, etc. In spite of their importance, very little attention has been paid to them. Particularly, a way to accurately characterize the structural hole spanners and the way to plot economical nevertheless scalable algorithms to seek out them in an exceedingly giant social network are elementary problems. In this paper, we have a tendency to study the prime-k structural hole spanner drawback. We have a tendency to 1st give a completely unique model to measure the quality of structural hole spanners through exploiting the structural hole spanner properties. Due to its NP-hardness, we then devise two efficient however scalable algorithms, by developing innovative filtering techniques that can filter out unlikely solutions as quickly as potential, whereas the proposed techniques are designed up on quick estimations of the higher and lower bounds on the value of an optimal solution and make use of articulation points in real social networks. We finally conduct extensive experiments to validate the effectiveness of the proposed model, and to evaluate the performance of the proposed algorithms using real world datasets. The experimental results demonstrate that the proposed model will capture the characteristics of structural hole spanners accurately, and the structural hole spanners found by the proposed algorithms are abundant better than those by existing algorithms in all considered social networks, while the running times of the proposed algorithms are very fast.