Data Mining
Fatemeh Akbari; Eynollah Khanjari
Abstract
Background and Objectives: So far, several methods have been proposed to detect communities, which indicate the high importance of discovering communities for understanding social networks and detecting useful and hidden patterns in the network. The goal of such analyses is to find a group of users with ...
Read More
Background and Objectives: So far, several methods have been proposed to detect communities, which indicate the high importance of discovering communities for understanding social networks and detecting useful and hidden patterns in the network. The goal of such analyses is to find a group of users with common characteristics. Basically, social networks are considered as graphs, so the analysis is also done using graph methods, in which nodes represent individuals and edges represent relationships between them. Since community detection is an NP-complete problem, several meta-heuristic approaches have been used to tackle this problem, mainly considering "modularity" as the objective function. In most approaches, modularity has been used, which suffers from the limitation of resolution and cannot detect communities that are small in size and consider it in combination with large communities.Methods: In this paper, a new hybrid algorithm of bee colony and genetics is proposed for community detection which performs optimization using the "balanced modularity" fitness function. In this algorithm, parallel processing is used to speed up optimization, genetic algorithm is used to create the initial population, and genetic operators are used in the search by bees.Results: Experiments on well-known real-world networks, including karate, American football, dolphins, and political books, have shown that our method provides more accurate results than the state-of-the-art community detection methods.Conclusion: The combined optimization of bee colony and genetics not only provides globally optimal solution but also it does not need prior information about the number as well as the structure of communities.
Social Networks
M. Sabzekar; S. Baradaran Nejad; M. Khazaeipoor
Abstract
Background and Objectives: Nowadays, social networks are recognized as significant sources of information exchange. Consequently, many organizations have chosen social networks as essential tools for marketing and brand management. Communities are essential structures that can enhance the performance ...
Read More
Background and Objectives: Nowadays, social networks are recognized as significant sources of information exchange. Consequently, many organizations have chosen social networks as essential tools for marketing and brand management. Communities are essential structures that can enhance the performance of social networks by grouping nodes and analyzing the information derived from them. This subject becomes more important with the increase in information volume and the complexity of relationships in networks. The goal of community identification is to find subgraphs that are densely connected internally but loosely connected externally.Methods: While community detection has mostly been studied in static networks in the past, this paper focuses on dynamic networks and the influence of central nodes in forming communities. In the proposed algorithm, the network is captured through multiple snapshots. The initial snapshot calculates the influence of each node. Then, by selecting k nodes with higher influence, network communities are formed, and other nodes belong to the community with the most common edges. In the second step, after receiving the next snapshot, communities are updated. Then, k nodes with higher influence are selected, and their associated community is created if needed. If the previous community centers are not among the newly selected k nodes, the community is dissolved, and the nodes within it belong to other communities.Results: Based on the results obtained, the proposed algorithm has managed to achieve better results in most cases compared to the compared algorithms, especially in terms of modularity metrics. The reason behind this success could be attributed to the utilization of influential nodes in community formation.Conclusion: Drawing from the outcomes attained, the suggested algorithm has effectively outperformed the contrasted algorithms in a majority of instances, particularly concerning metrics related to modularity. This accomplishment can potentially be ascribed to the incorporation of influential nodes during the process of community formation.
Data Science
H. Hajibabaei; V. Seydi; A. Koochari
Abstract
Background and Objectives: The detection of community in networks is an important tool for revealing hidden data in network analysis. One of the signs that the community exists in the network is the neighborhood density between nodes. Also, the existence of a concept called a motif indicates that a community ...
Read More
Background and Objectives: The detection of community in networks is an important tool for revealing hidden data in network analysis. One of the signs that the community exists in the network is the neighborhood density between nodes. Also, the existence of a concept called a motif indicates that a community with a high edge density has a correlation between nodes that go beyond their close neighbors. Motifs are repetitive edge patterns that are frequently seen in the network.Methods: By estimating the triangular motif in the network, our proposed probabilistic motif-based community detection model (PMCD) helps to find the communities in the network. The idea of the proposed model is network analysis based on structural density between nodes and detecting communities by estimating motifs using probabilistic methods.Results: The suggested model's output is the strength of each node's affiliation to the communities and detecting overlaps in communities. To evaluate the performance and accuracy of the proposed method, experiments are done on real-world and synthetic networks. The findings show that, compared to other algorithms, the proposed method is acting more accurately and densely in detecting communities.Conclusion: The advantage of PMCD in using the probabilistic generative model is speeding up the computation of the hidden parameters and establishing the community based on the likelihood of triangular motifs. In fact, the proposed method proves there is a probabilistic correlation between the observation of two node pairs in different communities and the increased existence of motif structure in the network.
Paralleling Louvain Community Detection
M. Mohammadi; M. Fazlali; M. Hosseinzadeh
Abstract
Background and Objectives: Louvain is a time-consuming community detection algorithm especially in large-scale networks. Using Graphic Processing Unit (GPU) in order to calculate modularity sigma, which is a major processing section in Louvain algorithm, can reduce algorithm execution time and make it ...
Read More
Background and Objectives: Louvain is a time-consuming community detection algorithm especially in large-scale networks. Using Graphic Processing Unit (GPU) in order to calculate modularity sigma, which is a major processing section in Louvain algorithm, can reduce algorithm execution time and make it practical for large-scale networks.Methods: The proposed algorithm Dynamic CUDA Louvain Method (DCLM) blocks hardware threads dynamically on cores inside GPU. By considering the properties of GPU, this algorithm allocates the maximal number of processing cores to each Stream Multi-Processor (SM) as number of threads in a block. If the number of nodes in the graph is smaller than all physical cores on GPU, number of threads per block Is equal to the ratio number of graph nodes over the number of SMs.Results: The implementation results demonstrated that the proposed algorithm is able to decrease the run time by 15% in comparison with the best past method in the large-scale graph.Conclusion: We have introduced DCLM algorithm based on GPU that accelerates Louvain community detection algorithm. Dynamic allocation of threads to each block has a significant effect on the reduction of algorithm execution time. However, incrementing the number of threads per block alone does not result to acceleration the speed of calculations.
Artificial Intelligence
S. Kianian; S. Farzi; H. Samak
Abstract
Background and Objectives: Simplicity and flexibility constitute the two basic features for graph models which has made them functional models for real life problems. The attributive graphs are too popular among researchers because of their efficiency and functionality. An attributive graph is a graph ...
Read More
Background and Objectives: Simplicity and flexibility constitute the two basic features for graph models which has made them functional models for real life problems. The attributive graphs are too popular among researchers because of their efficiency and functionality. An attributive graph is a graph the nodes and edges of which can be attributive. Nodes and edges as structural dimension and their attributes as contextual dimension made graphs more flexible in modeling real problems.Methods: In this study, a new clustering algorithm is proposed based on K-Medoid which focuses on graph’s structure dimension, through heat diffusion algorithm and contextual dimension through weighted Jaccard coefficient in a simultaneous matter. The calculated clusters through proposed algorithm are of denser and nodes with more similar attributes.Results: DBLP and PBLOG real data sets are applied to evaluate and compare this algorithm with new and well-known cluster algorithms.Conclusion: Results indicate the outperformers of this algorithm in relation to its counterparts as to structure quality, cluster contextual and time complexity criteria.
