A robust ant colony optimization-based algorithm for community mining in large scale oriented social graphs

Community detection plays a key role in such important fields as biology, sociology and computer science. For example, detecting the communities in protein–protein interactions networks helps in understanding their functionalities. Most existing approaches were devoted to community mining in undirected social networks (either weighted or not). In fact, despite their ubiquity, few proposals were interested in community detection in oriented social networks. For example, in a friendship network, the influence between individuals could be asymmetric; in a networked environment, the flow of information could be unidirectional. In this paper, we propose an algorithm, called ACODIG, for community detection in oriented social networks. ACODIG uses an objective function based on measures of density and purity and incorporates the information about edge orientations in the social graph. ACODIG uses ant colony for its optimization. Simulation results on real-world as well as power law artificial benchmark networks reveal a good robustness of ACODIG and an efficiency in computing the real structure of the network.     

Mixing local and global information for community detection in large networks

Clustering networks play a key role in many scientific fields, from Biology to Sociology and Computer Science. Some clustering approaches are called global because they exploit knowledge about the whole network topology. Vice versa, so-called local methods require only a partial knowledge of the network topology. Global approaches yield accurate results but do not scale well on large networks; local approaches, vice versa, are less accurate but computationally fast. We propose CONCLUDE (COmplex Network CLUster DEtection), a new clustering method that couples the accuracy of global approaches with the scalability of local methods. CONCLUDE generates random, non-backtracking walks of finite length to compute the importance of each edge in keeping the network connected, i.e., its edge centrality. Edge centralities allow for mapping vertices onto points of a Euclidean space and compute all-pairs distances between vertices; those distances are then used to partition the network into clusters.     

A framework for joint community detection across multiple related networks

Community detection in networks is an active area of research with many practical applications. However, most of the early work in this area has focused on partitioning a single network or a bipartite graph into clusters/communities. With the rapid proliferation of online social media, it has become increasingly common for web users to have noticeable presence across multiple web sites. This raises the question whether it is possible to combine information from several networks to improve community detection. In this paper, we present a framework that identifies communities simultaneously across different networks and learns the correspondences between them. The framework is applicable to networks generated from multiple web sites as well as to those derived from heterogeneous nodes of the same web site. It also allows the incorporation of prior information about the potential relationships between the communities in different networks. Extensive experiments have been performed on both synthetic and real-life data sets to evaluate the effectiveness of our framework. Our results show superior performance of simultaneous community detection over three alternative methods, including normalized cut and matrix factorization on a single network or a bipartite graph.     

An ANTS heuristic for the frequency assignment problem

The problem considered in this paper consists in assigning frequencies to radio links between base stations and mobile transmitters in order to minimize the global interference over a given region. This problem is NP-hard and few results have been reported on techniques for solving it to optimality. We have applied to this problem an ANTS metaheuristic, that is, an approach following the ant colony optimization paradigm. Computational results, obtained on a number of standard problem instances, testify the effectiveness of the proposed approach.     

A hybrid particle swarm optimization approach for the sequential ordering problem

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost.     

基于谱聚类的复杂网络社团发现算法

复杂网络社团发现的研究对于控制疾病传播、网络病毒的传播等具有重大意义.针对已有社团发现算法时间复杂度过高,不适用于结构未知的大型网络等问题,结合谱聚类在识别未知分布数据集聚类方面的优势,以及模块度函数能够在大型网络中搜寻出最佳社团数目的能力,提出了基于谱聚类的社团发现算法--SCCF算法.实验结果表明,与已有的社团发现算法相比,SCCF算法效率更高,并且能够在网络节点数上万的大型网络中得到高质量的社团结构.     

Multi-objective community detection in complex networks

Community detection in social network analysis is usually considered as a single objective optimization problem, in which different heuristics or approximate algorithms are employed to optimize a objective function that capture the notion of community. Due to the inadequacy of those single-objective solutions, this paper first formulates a multi-objective framework for community detection and proposes a multi-objective evolutionary algorithm for finding efficient solutions under the framework. After analyzing and comparing a variety of objective functions that have been used or can potentially be used for community detection, this paper exploits the concept of correlation between objective which charcterizes the relationship between any two objective functions. Through extensive experiments on both artifical and real networks, this paper demonstrates that a combination of two negatively correlated objectives under the multi-objective framework usually leads to remarkably better performance compared with either of the orignal single objectives, including even many popular algorithms..     

A vector partitioning approach to detecting community structure in complex networks

In recent years, the problem of community structure detection has attracted more and more attention and many approaches have been proposed. Recently, Newman pointed out that this issue can be transformed into the problem of constrained maximization of the assignment matrix over possible divisions of a network. He presents further that this maximization process can be written in terms of the eigenspectrum of the “modularity matrix”. On the basis of this work and the vector partition approach in computer science, we propose a kind of multiway division approach for detecting community structure of complex networks. Experimental results indicate that the algorithm works well and is effective at finding both good communities and the appropriate number of communities.     

复杂网络中的社团结构发现方法

社团结构是真实复杂网络异质性与模块化特性的反映。深入研究网络的社团结构有助于揭示错综复杂的真实网络是怎样由许多相对独立而又互相关联的社区形成的,使人们更好地理解系统不同层次的结构和功能,具有广泛的实用价值。总结了目前常用的社区发现方法,包括经典的GN算法、模块度优化算法、基于网络动力学的方法以及统计推断方法;用社区划分基准测试网络Zachary对上述算法进行了实验,对这几类算法的时间复杂度和优缺点进行了比较分析。最后,对复杂网络的社区结构发现算法的研究进行了展望。     

一种基于可变半衰期的机会网络社团兴趣值更新策略

为了掌握节点移动的历史信息,提出了MDIR (Mass-group Detected by Interest-value )算法。该算法引入了社团的概念,将节点的移动规律与其它节点的关系进行关联。理论上,在社会网络中节点的移动可以归结为在不同社团中移动的过程。因此在该算法中,消息更倾向于向包含目标节点的社团转发。此外,考虑到社会关系的动态性,算法还引入兴趣值概念来更新网络拓扑中的社团结构。实验测试数据表明,在不同的节点密集度和网络资源有限的情况下,相较于Epidemic、BDCR以及SREP算法,MDIR算法可通过计算效用值进行路由转发来产生较低的转发能耗以及稳定的送达率。     

A note on competitive diffusion through social networks

We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then an equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then an equilibrium is not guaranteed to exist.     

A study on visual sensor network cross-layer resource allocation using quality-based criteria and metaheuristic optimization algorithms

Visual sensor networks (VSNs) consist of spatially distributed video cameras that are capable of compressing and transmitting the video sequences they acquire. We consider a direct-sequence code division multiple access (DS-CDMA) VSN, where each node has its individual requirements in compression bit rate and energy consumption, depending on the corresponding application and the characteristics of the monitored scene. We study two optimization criteria for the optimal allocation of the source and channel coding rates, which assume discrete values, as well as for the power levels of all nodes, which are continuous, under transmission bit rate constraints. The first criterion minimizes the average distortion of the video received by all nodes, while the second one minimizes the maximum video distortion among all nodes. The resulting mixed integer optimization problems are tackled with a modern optimization algorithm, namely particle swarm optimization (PSO), as well as a hybrid scheme that combines PSO with the deterministic Active-Set optimization method. Extensive experimentation on interference-limited as well as noisy environments offers significant intuition regarding the effectiveness of the considered optimization schemes, indicating the impact of the video sequence characteristics on the joint determination of the transmission parameters of the VSN.     

核k-means聚类检测复杂网络社团算法

为揭示复杂系统中的结构与功能之间的联系,复杂网络中的社团发现成为一项最基本的任务.最近,李等人提出了一种用来评估社团质量的函数,称之为模块密度函数(即D值),并利用一个核矩阵给出了模块密度目标函数与核k-means方法之间的等价性.基于这种等价性,通过过渡操作的核矩阵来优化模块密度函数并提出了一种新的核k-means算法.实验结果表明,这种算法在发现复杂网络社团上是有效的.     

一种高效的大规模网络k团挖掘算法

网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k－1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c²_k)和O(c_k)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。     

基于社会计算和深度学习的社交网络特定内容监控

社交网络极大地方便了人们的生活,加速了信息的共享,但同时也被用于不良和敏感信息的传播,内容安全问题亟待解决。针对此类问题,提出了一套基于社会计算和深度学习的社交网络特定内容监控体系,首先基于成对监督信息实现以内容为导向的半监督社区发现,找到所关心的特定人群;然后对所挖掘的特定人群进行实时监控并获取其发布的内容,对图像和视频进行实时自动内容识别;同时针对实网数据误报多的问题提出面向多负类的误判修正方法,以达到收集实时信息,净化网络环境,在一定程度上预防犯罪的目的。     

基于SLPA优化的重叠社区发现算法

传统的重叠社区发现算法SLPA虽然具有时间复杂度和性能上的优势,但标签传播算法内在的随机策略使得算法结果并不稳定。针对SLPA的缺点,提出一种高效稳定的重叠社区发现算法L-SLPA。先对网络进行非重叠划分,减少不同标签分配的数量,同时加入边界节点的考虑进行剪枝,以提高运行速度。实验结果表明,相比于SLPA,该算法在降低运行时间和随机性的同时保证了结果的准确性。