Modeling network growth with assortative mixing

We propose a model of an underlying mechanism responsible for the formation of assortative mixing in networks between “similar” nodes or vertices based on generic vertex properties. Existing models focus on a particular type of assortative mixing, such as mixing by vertex degree, or present methods of generating a network with certain properties, rather than modeling a mechanism driving assortative mixing during network growth. The motivation is to model assortative mixing by non-topological vertex properties, and the influence of these non-topological properties on network topology. The model is studied in detail for discrete and hierarchical vertex properties, and we use simulations to study the topology of resulting networks. We show that assortative mixing by generic properties directly drives the formation of community structure beyond a threshold assortativity of r ∼0.5, which in turn influences other topological properties. This direct relationship is demonstrated by introducing a new measure to characterise the correlation between assortative mixing and community structure in a network. Additionally, we introduce a novel type of assortative mixing in systems with hierarchical vertex properties, from which a hierarchical community structure is found to result. Electronic supplementary material Supplementary Online Material     

Overlapping Community Detection Based on Membership Degree Propagation

A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.     

Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

Research on Community Structure in Bus Transport Networks

We abstract the bus transport networks (BTNs) to two kinds of complex networks with space L and space P methods respectively. Using improved community detecting algorithm (PKM agglomerative algorithm), we analyze the community property of two kinds of BTNs graphs. The results show that the BTNs graph described with space L method have obvious community property, but the other kind of BTNs graph described with space P method have not. The reason is that the BTNs graph described with space P method have the intense overlapping community property and general community division algorithms can not identify this kind of community structure. To overcome this problem, we propose a novel community structure called N-depth community and present a corresponding community detecting algorithm, which can detect overlapping community. Applying the novel community structure and detecting algorithm to a BTN evolution model described with space P, whose network property agrees well with real BTNs', we get obvious community property.     

Graph kernels,hierarchical clustering,and network community structure: experiments and comparative analysis

There has been a quickly growing interest in properties of complex networks, such as the small world property, power-law degree distribution, network transitivity, and community structure, which seem to be common to many real world networks. In this study, we consider the community property which is also found in many real networks. Based on the diffusion kernels of networks, a hierarchical clustering approach is proposed to uncover the community structure of different extent of complex networks. We test the method on some networks with known community structures and find that it can detect significant community structure in these networks. Comparison with related methods shows the effectiveness of the method.     

Fuzzy overlapping community detection based on local random walk and multidimensional scaling

A fuzzy overlapping community is an important kind of overlapping community in which each node belongs to each community to different extents. It exists in many real networks but how to identify a fuzzy overlapping community is still a challenging task. In this work, the concept of local random walk and a new distance metric are introduced. Based on the new distance measurement, the dissimilarity index between each node of a network is calculated firstly. Then in order to keep the original node distance as much as possible, the network structure is mapped into low-dimensional space by the multidimensional scaling (MDS). Finally, the fuzzy c$c$-means clustering is employed to find fuzzy communities in a network. The experimental results show that the proposed algorithm is effective and efficient to identify the fuzzy overlapping communities in both artificial networks and real-world networks.     

A High-Order Accurate Algorithm for Electrostatics of Overlapping Disks

A fast and accurate algorithm for the computation of effective electric and mathematically equivalent properties of composites with nonsmooth interfaces is reported. The algorithm is based on an integral equation reformulation of the electrostatic partial differential equation and a fast hierarchical technique for potential field evaluation. In a numerical example, 200 large and strongly inhomogeneous aggregates of randomly overlapping disks are solved with a relative error of 0.0005.     

Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods.     

Detecting overlapping communities in networks via dominant label propagation

Community detection is an important methodology for understanding the intrinsic structure and function of a realworld network.In this paper,we propose an effective and efficient algorithm,called Dominant Label Propagation Algorithm(Abbreviated as DLPA),to detect communities in complex networks.The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously.Our algorithm is very efficient,since its computational complexity is almost linear to the number of edges in the network.Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.     

Detecting hierarchical and overlapping network communities using locally optimal modularity changes

Agglomerative clustering is a well established strategy for identifying communities in networks. Communities are successively merged into larger communities, coarsening a network of actors into a more manageable network of communities. The order in which merges should occur is not in general clear, necessitating heuristics for selecting pairs of communities to merge. We describe a hierarchical clustering algorithm based on a local optimality property. For each edge in the network, we associate the modularity change for merging the communities it links. For each community vertex, we call the preferred edge that edge for which the modularity change is maximal. When an edge is preferred by both vertices that it links, it appears to be the optimal choice from the local viewpoint. We use the locally optimal edges to define the algorithm: simultaneously merge all pairs of communities that are connected by locally optimal edges that would increase the modularity, redetermining the locally optimal edges after each step and continuing so long as the modularity can be further increased. We apply the algorithm to model and empirical networks, demonstrating that it can efficiently produce high-quality community solutions. We relate the performance and implementation details to the structure of the resulting community hierarchies. We additionally consider a complementary local clustering algorithm, describing how to identify overlapping communities based on the local optimality condition.     

Community detection in networks by using multiobjective evolutionary algorithm with decomposition

Community structure is an important property of complex networks. Most optimization-based community detection algorithms employ single optimization criteria. In this study, the community detection is solved as a multiobjective optimization problem by using the multiobjective evolutionary algorithm based on decomposition. The proposed algorithm maximizes the density of internal degrees, and minimizes the density of external degrees simultaneously. It can produce a set of solutions which can represent various divisions to the networks at different hierarchical levels. The number of communities is automatically determined by the non-dominated individuals resulting from our algorithm. Experiments on both synthetic and real-world network datasets verify that our algorithm is highly efficient at discovering quality community structure.     

Detecting overlapping communities based on vital nodes in complex networks

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm(DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.     

Efficient overlapping community detection in huge real-world networks

The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments.     

Detecting overlapping communities of weighted networks via a local algorithm

Identification of communities is significant in understanding the structures and functions of networks. Since some nodes naturally belong to several communities, the study of overlapping communities has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. In this paper, an overlapping communities detecting algorithm is proposed whose main strategies are finding an initial partial community from a node with maximal node strength and adding tight nodes to expand the partial community. Seven real-world complex networks and one synthetic network are used to evaluate the algorithm. Experimental results demonstrate that the algorithm proposed is efficient for detecting overlapping communities in weighted networks.     

A game theoretic algorithm to detect overlapping community structure in networks

Community detection can be used as an important technique for product and personalized service recommendation. A game theory based approach to detect overlapping community structure is introduced in this paper. The process of the community formation is converted into a game, when all agents (nodes) cannot improve their own utility, the game process will be terminated. The utility function is composed of a gain and a loss function and we present a new gain function in this paper. In addition, different from choosing action randomly among join, quit and switch for each agent to get new label, two new strategies for each agent to update its label are designed during the game, and the strategies are also evaluated and compared for each agent in order to find its best result. The overlapping community structure is naturally presented when the stop criterion is satisfied. The experimental results demonstrate that the proposed algorithm outperforms other similar algorithms for detecting overlapping communities in networks.     

Detecting overlapping communities by seed community in weighted complex networks

Detection of community structures in the weighted complex networks is significant to understand the network structures and analysis of the network properties. We present a unique algorithm to detect overlapping communities in the weighted complex networks with considerable accuracy. For a given weighted network, all the seed communities are first extracted. Then to each seed community, more community members are absorbed using the absorbing degree function. In addition, our algorithm successfully finds common nodes between communities. The experiments using some real-world networks show that the performance of our algorithm is satisfactory.     

Detection of community structure in networks based on community coefficients

Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function Q$Q$, which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity Q$Q$ is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient C$C$. Using community coefficient C$C$, we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient C$C$ is superior to the modularity Q$Q$ and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient C$C$ were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities.     

Overlapping Community Detection Based on Attribute Augmented Graph

There is a wealth of information in real-world social networks. In addition to the topology information, the vertices or edges of a social network often have attributes, with many of the overlapping vertices belonging to several communities simultaneously. It is challenging to fully utilize the additional attribute information to detect overlapping communities. In this paper, we first propose an overlapping community detection algorithm based on an augmented attribute graph. An improved weight adjustment strategy for attributes is embedded in the algorithm to help detect overlapping communities more accurately. Second, we enhance the algorithm to automatically determine the number of communities by a node-density-based fuzzy k-medoids process. Extensive experiments on both synthetic and real-world datasets demonstrate that the proposed algorithms can effectively detect overlapping communities with fewer parameters compared to the baseline methods.     

BiOCl nanowire with hierarchical structure and its Raman features

BiOCl is a promising V-VI-VII-compound semiconductor with excellent optical and electrical properties, and has great potential applications in photo-catalysis, photoelectric, etc. We successfully synthesize BiOCl nanowire with a hierarchical structure by combining wet etch (top-down) with liquid phase crystal growth (bottom-up) process, opening a novel method to construct ordered bismuth-based nanostructures. The morphology and lattice structures of Bi nanowires, β-Bi₂O₃ nanowires and BiOCl nanowires with the hierarchical structure are investigated by scanning electron microscope (SEM) and transition electron microscope (TEM). The formation mechanism of such ordered BiOCl hierarchical structure is considered to mainly originate from the highly preferred growth, which is governed by the lattice match between (1 1 0) facet of BiOCl and (2 2 0) or (0 0 2) facet of β-Bi₂O₃. A schematic model is also illustrated to depict the formation process of the ordered BiOCl hierarchical structure. In addition, Raman properties of the BiOCl nanowire with the hierarchical structure are investigated deeply.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.