Betweenness centrality-based community adaptive network representation for link prediction
14
Citation
38
Reference
10
Related Paper
Citation Trend
Keywords:
Representation
Link (geometry)
Dynamic network analysis
Considering the high computational complexity of Closeness Centrality and the structural characteristics of community in complex networks, The BridgeRank (BR) algorithm to evaluate node importance of complex networks based on community division is proposed. The complex network is divided into several communities. The node with the largest local betweenness centrality in each community is extracted as the keynode of the community. The importance ranking of nodes is obtained by adopting the BR algorithm to caculate the sum of the shortest paths from each node to these key nodes in the network. The BR algorithm is achieved based on the Kernighan-Lin, Girvan-Newman, Newman fast and Louvain algorithm respectively. The experimental shows that BR algorithm based on Louvain community division has the highest accuracy in estimating node importance. On the basis that Community Size BridgeRank (CS-BR) and the Local Betweenness Centrality BridgeRank (LBC-BR) are proposed based on the size of the community and the weight of the local betweenness centrality of key nodes respectively. The experiments results on four detasets show that compared with some classic algorithms, the important nodes evaluated by the three proposed methods have stronger spread ability in SIR model, Moreover,the improved CS-BR and LBC-BR algorithm are better than BR.
Closeness
Cite
Citations (0)
Evaluating the centrality of nodes in complex networks is one of the major research topics being explored due to its wide range of applications. Among the various measures that have been developed over the years, Betweenness centrality is one of the most popular. Indeed, it has proved to be efficient in many real-world situations. In this paper, we propose an extension of the Betweenness centrality designed for networks with nonoverlapping community structure. It is a linear combination of the so-called "local" and "global" Betweenness measures. The Local measure takes into account the influence of a node at the community level while the global measure depends only on the interactions between the communities. Depending of the community structure strength, more or less importance is given to each of these two elements. By using the Susceptible-Infected-Recovered (SIR) model in epidemic spreading simulations, we show that the "Weighted Community Betweenness" centrality is more efficient than the traditional Betweenness which is agnostic of the community structure. The proposed measure stands out also the traditional measure by its low complexity, allowing its use in very large scale networks.
Cite
Citations (17)
Social network comprise of social entities that are linked together with ties. The abundant use of social medias like Facebook, Instagram, Flicker, Youtube, Twitter, etc. leads to the evolution of more networks those are large, dynamic and complicated in nature. Social network can be represented as a graph structure where each node represents as an individual and each edge represents as a relation between the individuals. Community detection in social network plays a vital role in predicting the insights present in the complex network and hence is a very challenging task too. Community structure solves many real world problems by providing different solutions. Community is a collection of group of nodes where internal density of the edges is more and nodes are sparsely connected to the nodes of the other community. The nodes present inside a community exhibits similar kind properties and all are influenced by the central node of that particular community. Hence centrality detection mechanism is used to detect the central node of the network and further it is used to identify the communities present over the network. In order to minimize the computational time, MapReduce approach is adopted to determine the degree centrality values for each and every node. Finally communities are detected using identified central nodes. The results show that proposed method is more efficient in accuracy and time complexity as compared to other existing algorithms.
Social network (sociolinguistics)
Social Network Analysis
Cite
Citations (0)
The phenomena of community structure in real-world networks has been central to network science's success. While much attention has been paid to community detection algorithms and evaluation criteria, a related question has been overlooked: what would the change in modularity be if a node were to be deleted from a network? In this work, we first show that the answer to this question can be calculated for all nodes in the network in $O(m)$ time. Then, we show that this quantity has implications in three research areas within network science: community analysis, network robustness, and community deception. Modularity-deltas are useful in community analysis as they are a semi-global measure, scalable like local measures but using global information through the network's this http URL robustness, modularity maximizing attack strategies are more efficient than betweenness-based ones, and are shown to damage the US Powergrid and European Road networks more effectively than degree based attacks. Finally, we show that inverting the robustness method to select modularity minimizing nodes solves the community deception problem in a scalable manner.
Robustness
Modularity
Network Analysis
Cite
Citations (0)
Complex networks are suitable for modeling real world systems. A multilayer network is a complex network, where each node establishes relationships with other nodes, across the layers. Ranking of nodes in multilayer networks is considered to be a key research problem for analyzing the dynamics of networks. In general, nodes are ranked using metrics such as degree centrality, betweenness centrality, and PageRank. However, these metrics are not suitable for multilayer networks, since rank may not display the actual influence of a node. This paper proposes a novel ranking metric m-PageRank for finding influential nodes in the multilayer network. Experiments using real dataset show the benefits of proposed metric.
PageRank
Rank (graph theory)
Benchmark (surveying)
Learning to Rank
Cite
Citations (15)
Many of real-world social networks, show structural changes over time, so they can be modeled as dynamic graphs. However, most methods in social network analysis, including community detection, are focused on performing on static networks. Therefore, methods of studying community evolution still have room for improvement. In this article, we investigated one of the methods introduced in independent community detection and matching approach. It is an approach for tracking dynamic community evolution, but it has the advantage of using methods that have been studied in detail for static networks. Previous studies have examined and compared some of the centralities that can be used in this method. In this study, we examined its performance by using other centralities called betweenness centrality and closeness centrality, and compared them with the usage of social position. Our analysis was performed on a subgraph of the word co-occurrence network, which is a type of bibliometric network, and the results of the algorithm were evaluated by experts. The results show that betweenness centrality represents more transparent and useful events and using it in community evolution discovery is recommended for small networks.
Closeness
Social Network Analysis
Network Analysis
Dynamic network analysis
Network theory
Social network (sociolinguistics)
Cite
Citations (0)
With its origin in sociology, Social Network Analysis (SNA), quickly emerged and spread to other areas of research, including anthropology, biology, information science, organizational studies, political science, and computer science. Being it's objective the investigation of social structures through the use of networks and graph theory, Social Network Analysis is, nowadays, an important research area in several domains. Social Network Analysis cope with different problems namely network metrics, models, visualization and information spreading, each one with several approaches, methods and algorithms. One of the critical areas of Social Network Analysis involves the calculation of different centrality measures (i.e.: the most important vertices within a graph). Today, the challenge is how to do this fast and efficiently, as many increasingly larger datasets are available. Recently, the need to apply such centrality algorithms to non static networks (i.e.: networks that evolve over time) is also a new challenge. Incremental and dynamic versions of centrality measures are starting to emerge (betweenness, closeness, etc). Our contribution is the proposal of two incremental versions of the Laplacian Centrality measure, that can be applied not only to large graphs but also to, weighted or unweighted, dynamically changing networks. The experimental evaluation was performed with several tests in different types of evolving networks, incremental or fully dynamic. Results have shown that our incremental versions of the algorithm can calculate node centralities in large networks, faster and efficiently than the corresponding batch version in both incremental and full dynamic network setups.
Social Network Analysis
Dynamic network analysis
Network theory
Closeness
Network Analysis
Evolving networks
Social network (sociolinguistics)
Cite
Citations (1)
With its origin in sociology, Social Network Analysis (SNA), quickly emerged and spread to other areas of research, including anthropology, biology, information science, organizational studies, political science, and computer science. Being it's objective the investigation of social structures through the use of networks and graph theory, Social Network Analysis is, nowadays, an important research area in several domains. Social Network Analysis cope with different problems namely network metrics, models, visualization and information spreading, each one with several approaches, methods and algorithms. One of the critical areas of Social Network Analysis involves the calculation of different centrality measures (i.e.: the most important vertices within a graph). Today, the challenge is how to do this fast and efficiently, as many increasingly larger datasets are available. Recently, the need to apply such centrality algorithms to non static networks (i.e.: networks that evolve over time) is also a new challenge. Incremental and dynamic versions of centrality measures are starting to emerge (betweenness, closeness, etc). Our contribution is the proposal of two incremental versions of the Laplacian Centrality measure, that can be applied not only to large graphs but also to, weighted or unweighted, dynamically changing networks. The experimental evaluation was performed with several tests in different types of evolving networks, incremental or fully dynamic. Results have shown that our incremental versions of the algorithm can calculate node centralities in large networks, faster and efficiently than the corresponding batch version in both incremental and full dynamic network setups.
Social Network Analysis
Dynamic network analysis
Closeness
Network Analysis
Network theory
Evolving networks
Social network (sociolinguistics)
Organizational network analysis
Cite
Citations (0)
Representation
Link (geometry)
Dynamic network analysis
Cite
Citations (14)
Identification
Clique percolation method
Clustering coefficient
Cite
Citations (4)