Seed-Oriented Local Community Detection Based on Influence Spreading

In recent years,local community detection algorithms have developed rapidly because of their nearly linear computing time and the convenience of obtaining the local information of real-world networks.However,there are still some issues that need to be further studied.First,there is no local community detection algorithm dedicated to detecting a seed-oriented local community,that is,the local community with the seed as the core.The second and third issues are that the quality of local communities detected by the previous local community detection algorithms are largely dependent on the position of the seed and predefined parameters,respectively.To solve the existing problems,we propose a seed-oriented local community detection algorithm,named SOLCD,that is based on influence spreading.First,we propose a novel measure of node influence named k-core centrality that is based on the k-core value of adjacent nodes.Second,we obtain the seed-oriented local community,which is composed of the may-members and the must-member chain of the seed,by detecting the influence scope of the seed.The may-members and the must-members of the seed are determined by judging the influence relationship between the node and the seed.Five state-of-art algorithms are compared to SOLCD on six real-world networks and three groups of artificial networks.The experimental results show that SOLCD can achieve a high-quality seed-oriented local community for various real-world networks and artificial networks with different parameters.In addition,when taking nodes with different influence as seeds,SOLCD can stably obtain high-quality seed-oriented local communities.

Extremal Coalitions for Influence Games Through Swarm Intelligence-Based Methods

An influence game is a simple game represented over an influence graph(i.e.,a labeled,weighted graph)on which the influence spread phenomenon is exerted.Influence games allow applying different properties and parameters coming from cooperative game theory to the contexts of social network analysis,decision-systems,voting systems,and collective behavior.The exact calculation of several of these properties and parameters is computationally hard,even for a small number of players.Two examples of these parameters are the length and the width of a game.The length of a game is the size of its smaller winning coalition,while the width of a game is the size of its larger losing coalition.Both parameters are relevant to know the levels of difficulty in reaching agreements in collective decision-making systems.Despite the above,new bio-inspired metaheuristic algorithms have recently been developed to solve the NP-hard influence maximization problem in an efficient and approximate way,being able to find small winning coalitions that maximize the influence spread within an influence graph.In this article,we apply some variations of this solution to find extreme winning and losing coalitions,and thus efficient approximate solutions for the length and the width of influence games.As a case study,we consider two real social networks,one formed by the 58 members of the European Union Council under nice voting rules,and the other formed by the 705 members of the European Parliament,connected by political affinity.Results are promising and show that it is feasible to generate approximate solutions for the length and width parameters of influence games,in reduced solving time.

Identifying spreading influence nodes for social networks

The identification of spreading influence nodes in social networks,which studies how to detect important individuals in human society,has attracted increasing attention from physical and computer science,social science and economics communities.The identification algorithms of spreading influence nodes can be used to evaluate the spreading influence,describe the node’s position,and identify interaction centralities.This review summarizes the recent progress about the identification algorithms of spreading influence nodes from the viewpoint of social networks,emphasizing the contributions from physical perspectives and approaches,including the microstructure-based algorithms,community structure-based algorithms,macrostructure-based algorithms,and machine learning-based algorithms.We introduce diffusion models and performance evaluation metrics,and outline future challenges of the identification of spreading influence nodes.