• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Natalia Meshcheryakova
Analysis of Graph Centralities with the Help of Shapley Values
9
2016
The topic of the present research paper refers to the analysis of the social networks’ characteristics. The paper touches upon key questions evaluating the power and the influence of network participants. The objective of this study is to describe and compare existing methodologies with the one that is explored in this paper. The techniques employed are based on the game theory approach and refer to the Shapley value calculation. The research is undertaken to develop a potentially powerful method of approximate calculation of the Shapley value in order to find a balance between computational complexity and the calculation accuracy. The objects under study are exponentially distributed random networks with different graph characteristics. Different applications of the approach based on simple paths between nodes are also proposed in the current work. Experimental results highlight advantages and disadvantages of different approximation methodologies. The comparison with other measures shows that the proposed methodology detects central nodes as expected.

Keywords: Social Network Analysis, Shapley Values, Key Nodes, Approximation Methods, Simple Paths, Randomized algorithms.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses