The design of centrality metric algorithms to distinguish influential nodes on networks has become a very attractive research interest lately. This recent development is due to the fact that detection of powerful node...
详细信息
The design of centrality metric algorithms to distinguish influential nodes on networks has become a very attractive research interest lately. This recent development is due to the fact that detection of powerful nodes can be very helpful in various situations such as containment of epidemic spread and so on. Many useful centrality algorithms had been proposed in the past but some of them have inherent shortcomings. Some of these algorithms are designed to capture global or local network details but little efforts have been channeled to explore techniques based on sub-graph information. Therefore, a novel sub-graph degree-based bridge centrality (SDBC) algorithm to distinguish bridge nodes on networks is proposed in this work. A pivot node's sphere of influence is captured and this includes its 1-hop and 2-hop neighborhood with itself inclusive. A model is proposed to reduce links of all 2-hop neighbors to 1-hop links. The sub-graph degree distribution of all nodes under the pivot node's sphere of influence is computed and afterwards, the pivot node's bridging influence capacity is quantified using Dehmer's entropy model. The proposed algorithm is designed to capture the topological and strength of connections between nodes. In essence, a tuning parameter is used to automatically switch between unweighted and weighted networks, a feature that makes the algorithm unique. Additionally, SDBC does not use two factor computation unlike previous bridge node detection algorithms. Various experimental comparisons were carried out against some selected centrality metrics and SDBC performed well against the compared algorithms. The results prove that the proposed method is quite efficient in distinguishing bridge nodes on complex networks.
The most key areas of transportation networks are the intersections that form the intersection points of the roads. The location of the intersections and the roads that they connect to are one of the most important fa...
详细信息
The most key areas of transportation networks are the intersections that form the intersection points of the roads. The location of the intersections and the roads that they connect to are one of the most important factors affecting the traffic flow. In this study, the importance of the intersection points on the streets and boulevards in the downtown of Malatya province in the transportation system will be determined. Population information has been calculated according to the city's land use plan. Intersection serving more than 90 percent of the population have been selected. Graph modeling made for Malatya downtown consists of 151 intersection points and 258 roads connecting these intersection points. The actual distance lengths of the roads are included in the graph modeling in meters. pagerank, eigenvector, closeness and betweenness centrality algorithms were applied on the weighted graph created. The properties and results of each algorithm are examined in detail. A homogeneous combining approach that contains all the unique features of these 4 algorithms has been applied and successful results have been obtained. The centrality values of the intersection points and the most effective intersection point are shown on the graph according to the results of all algorithms. R programming language was used for all analysis and visual operations.
In this study, a method has been developed for solving the maximum independent set problem, which is one of the significant problems in graph theory. The maximum independent set problem is NP-hard for all types of gra...
详细信息
In this study, a method has been developed for solving the maximum independent set problem, which is one of the significant problems in graph theory. The maximum independent set problem is NP-hard for all types of graphs. The proposed method features a robust and greedy approach that produces results in polynomial time for all graph types. The proposed method is named the Differential Malatya Independent Set algorithm (DMISA). The presented method also provides solutions to the minimum vertex cover and maximum clique problems, which are directly related to the independent set. The DMISA algorithm consists of two sub-algorithms. The first algorithm is the Differential Malatya centrality algorithm (DMCA), a centrality algorithm that calculates centrality values, providing prioritization in the selection of independent members. The second algorithm uses the DMCA value to select the independent set and vertex cover members in the graphs. In this study, the DMISA analytical proof has been applied to graphs with known solutions that can be solved in polynomial time. To emphasize the success of the algorithm, test operations have been conducted on various types of graphs. The conducted tests included 40 lattices, 40 bipartite, 24 multipartite, 32 social, and random graphs. The analysis results showed that DMISA produced optimal results in lattice, bipartite, and complete multipartite graphs, while it produced generally non-optimal results for randomly generated and social graphs. Additionally, DMISA is compared with MIS methods in popular graph libraries and 7 different MIS methods. In summary, DMISA produces a larger solution than standard greedy algorithms in experiments.
The minimum vertex-cover problem (MVCP) is an NP-complete optimization problem widely used in areas such as graph theory, social network, security and transportation, etc. Different approaches and algorithms have been...
详细信息
The minimum vertex-cover problem (MVCP) is an NP-complete optimization problem widely used in areas such as graph theory, social network, security and transportation, etc. Different approaches and algorithms have been proposed in the literature to solve this problem, since MVCP is an optimization problem, the solutions developed for this problem could be more intuitive and give results under certain constraints. In addition, the proposed solution methods for this problem could be more effective, and the determined solution sets change in each iteration. The algorithms/methods developed for solving MVCP are mostly based on heuristic or greedy approaches. This study presents the Malatya vertex-cover algorithm, which provides an efficient solution and a robust approach based on the Malatya centrality value algorithm for MVCP. Although MVCP is an NP-complete problem that cannot be solved in polynomial time, the proposed method offers a polynomial solution to this problem, and the obtained solutions are optimum or near-optimum (optimal solution). This algorithm consists of two basic steps. In the first step, the Malatya centrality values of the nodes in the graph are calculated using the Malatya centrality algorithm. The Malatya centrality value of the nodes in any graph is the summation of the ratio of the node's degree to the adjacent nodes' degrees for each node. In the second step, nodes are selected for the MVCP solution based on the node with the maximum Malatya centrality value (psi) in the graph is selected and added to the solution set. Then this node and the edges incident on this node are removed from the graph. For the graph consisting of the remaining nodes, Malatya centrality values are calculated again, and the selection process is continued. The process is terminated when all edges in the graph are covered. The proposed algorithm has been tested on artificial, actual graphs and large-scale random graphs produced with the Erdos-Renyi model. When the result
Microblogging platforms have emerged as large collections of short documents, which have been growing in term of size and volume. In fact, providing an effective way to add semantics to this form of communication pres...
详细信息
ISBN:
(纸本)9781479935666
Microblogging platforms have emerged as large collections of short documents, which have been growing in term of size and volume. In fact, providing an effective way to add semantics to this form of communication present a significant research challenge because his noisy and inconsistency nature. Named Entity Linking (NEL) is a subtask of information extraction that aims to ground entity mentions to their corresponding node in a Knowledge Base (KB), which requires a disambiguation step, because many resources can be matched to the same entity that lead to synonymy and polysemy problems. To overcome such problems especially in the context of short text, we present a robust system for automatically extract named entities, disambiguating and linking them to knowledge base resources, based on graph centrality algorithm and Linked Open Data (LOD) paradigm. Also, we evaluate our system using a real twitter dataset [1] and comparing it with a public tool to show his effectiveness.
Twitter has became an invaluable source of information, due to his dynamic nature with more than 400 million tweets posted per day. Determining what an individual post is about can be a non trivial task because his hi...
详细信息
ISBN:
(纸本)9781479971008
Twitter has became an invaluable source of information, due to his dynamic nature with more than 400 million tweets posted per day. Determining what an individual post is about can be a non trivial task because his high contextualization and his informal nature. Named Entity Linking (NEL) is a subtask of information extraction that aims to ground entity mentions to their corresponding node in a Knowledge Base (KB), which requires a disambiguation step, because many resources can be matched to the same entity that lead to synonymy and polysemy problems. To overcome these problems, especially in the context of short text, we present a novel system for tweet entity linking based on graph centrality and DBpedia as knowledge base. Our approach relies on the assumption that related entities tend to appear in the same tweet as tweets are topic specific. Also, we address the problem of irregular name mentions. Finally, to show the effectiveness of our system we evaluate it using a real twitter dataset and compare it to a well known state-of-the-art named entity linking system for short text.
The prediction of essential proteins, the minimal set required for a living cell to support cellular life, is an important task to understand the cellular processes of an organism. Fast progress in high-throughput tec...
详细信息
The prediction of essential proteins, the minimal set required for a living cell to support cellular life, is an important task to understand the cellular processes of an organism. Fast progress in high-throughput technologies and the production of large amounts of data enable the discovery of essential proteins at the system level by analyzing Protein-Protein Interaction (PPI) networks, and replacing biological or chemical experiments. Furthermore, additional gene-level annotation information, such as Gene Ontology (GO) terms, helps to detect essential proteins with higher accuracy. Various centrality algorithms have been used to determine essential proteins in a PPI network, and, recently motif centrality GO, which is based on network motifs and GO terms, works best in detecting essential proteins in a Baker's yeast Saccharomyces cerevisiae PPI network, compared to other centrality algorithms. However, each centrality algorithm contributes to the detection of essential proteins with different properties, which makes the integration of them a logical next step. In this paper, we construct a new feature space, named CENT-ING-GO consisting of various centrality measures and GO terms, and provide a computational approach to predict essential proteins with various machine learning techniques. The experimental results show that CENT-ING-GO feature space improves performance over the INT-GO feature space in previous work by Acencio and Lemke in 2009. We also demonstrate that pruning a PPI with informative GO terms can improve the prediction performance further.
暂无评论