TMTomasz Pawel Michalak

Tomasz Pawel Michalak

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Tomasz Pawel Michalak has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Hiding Individuals and Communities in a Social Network

    by Marcin Waniek, Tomasz Michalak, Talal Rahwan, Michael Wooldridge

    The Internet and social media have fueled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections, with particular emphasis on detecting communities or identifying key individuals in a social network. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question: Can individuals or groups actively manage their connections to evade social network analysis tools? By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence, and security agencies may better understand how terrorists escape detection. We first study how an individual can evade "network centrality" analysis without compromising his or her influence within the network. We prove that an optimal solution to this problem is hard to compute. Despite this hardness, we demonstrate that even a simple heuristic, whereby attention is restricted to the individual's immediate neighbourhood, can be surprisingly effective in practice. For instance, it could disguise Mohamed Atta's leading position within the WTC terrorist network, and that is by rewiring a strikingly-small number of connections. Next, we study how a community can increase the likelihood of being overlooked by community-detection algorithms. We propose a measure of concealment, expressing how well a community is hidden, and use it to demonstrate the effectiveness of a simple heuristic, whereby members of the community either "unfriend" certain other members, or "befriend" some non-members, in a coordinated effort to camouflage their community.

  • Efficient algorithms for game-theoretic betweenness centrality

    by Piotr L. Szczepański, Tomasz P. Michalak, Talal Rahwan


  • Open Access

    How good is the Shapley value-based approach to the influence maximization problem?

    by Kamil Adamczewski, Szymon Matejczyk, Tomasz P. Michalak

    The Shapley value has been recently advocated as a method to choose the seed nodes for the process of information diffusion. Intuitively, since the Shapley value evaluates the average marginal contribution of a player to the coalitional game, it can be used in the network context to evaluate the marginal contribution of a node in the process of information diffusion given various groups of already 'infected' nodes. Although the above direction of research seems promising, the current liter- ature is missing a throughout assessment of its performance. The aim of this work is to provide such an assessment of the existing Shapley value-based approaches to information diffusion.

  • Open Access

    Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality

    by Tomasz Pawel Michalak, Karthik V Aadithya, Piotr L. Szczepanski, Balaraman Ravindran, Nicholas R. Jennings

    The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.