A new clustering method and its application in social networks

In a graph theory model, clustering is the process of division of vertices into groups, with a higher density of edges within groups than between them. In this paper, we introduce a new clustering method for detecting such groups and use it to analyse some classic social networks. The new method has two distinguished features: non-binary hierarchical tree and the feature of overlapping clustering. A non-binary hierarchical tree is much smaller than the binary-trees constructed by most traditional methods and, therefore, it clearly highlights meaningful clusters which significantly reduces further manual efforts for cluster selections. The present method is tested by several bench mark data sets for which the community structure was known beforehand and the results indicate that it is a sensitive and accurate method for extracting community structure from social networks.     

An efficient algorithm for community mining with overlap in social networks

Detecting communities in social networks represents a significant task in understanding the structures and functions of networks. Several methods are developed to detect disjoint partitions. However, in real graphs vertices are often shared between communities, hence the notion of overlap. The study of this case has attracted, recently, an increasing attention and many algorithms have been designed to solve it. In this paper, we propose an overlapping communities detecting algorithm called DOCNet (Detecting overlapping communities in Networks). The main strategy of this algorithm is to find an initial core and add suitable nodes to expand it until a stopping criterion is met. Experimental results on real-world social networks and computer-generated artificial graphs demonstrate that DOCNet is efficient and highly reliable for detecting overlapping groups, compared with four newly known proposals.     

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.     

Cluster editing problem for points on the real line: A polynomial time algorithm

In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs.     

Searching for people to follow in social networks

With the development of social networks, more and more users have a great need to search for people to follow (SPTF) to receive their tweets. According to our experiments, approximately 50% of social networks’ lost users leave due to a lack of people to follow. In this paper, we define the problem of SPTF and propose an approach to give users tags and then deliver a ranked list of valuable accounts for them to follow. In the proposed approach, we first seek accounts related to keywords via expanding and predicting tags for users. Second, we propose two algorithms to rank relevant accounts: the first mines the forwarded relationship, and the second incorporates the following relationship into PageRank. Accordingly, we have built a search system¹ that to date, has received more than 1.7 million queries from 0.2 million users. To evaluate the proposed approach, we created a crowd-sourcing organization and crawled 0.25 billion profiles, 15 billion messages and 20 billion links representing following relationships on Sina Microblog. The empirical study validates the effectiveness of our algorithms for expanding and predicting tags compared to the baseline. From query logs, we discover that hot queries include keywords related to academics, occupations and companies. Experiments on those queries show that PageRank-like algorithms perform best for occupation-related queries, forward-relationship-like algorithms work best for academic-related queries and domain-related headcount algorithms work best for company-related queries.     

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.     

Evolving modular networks with genetic algorithms: application to nonlinear time series

Abstract: A key problem of modular neural networks is finding the optimal aggregation of the different subtasks (or modules) of the problem at hand. Functional networks provide a partial solution to this problem, since the inter‐module topology is obtained from domain knowledge (functional relationships and symmetries). However, the learning process may be too restrictive in some situations, since the resulting modules (functional units) are assumed to be linear combinations of selected families of functions. In this paper, we present a non‐parametric learning approach for functional networks using feedforward neural networks for approximating the functional modules of the resulting architecture; we also introduce a genetic algorithm for finding the optimal intra‐module topology (the appropriate balance of neurons for the different modules according to the complexity of their respective tasks). Some benchmark examples from nonlinear time‐series prediction are used to illustrate the performance of the algorithm for finding optimal modular network architectures for specific problems.     

On packing arborescences in temporal networks

A temporal network is a directed graph in which each arc has a time label specifying the time at which its end vertices communicate. An arborescence in a temporal network is said to be time-respecting, if the time labels on every directed path from the root in this arborescence are monotonically non-decreasing. In this paper, we consider a characterization of the existence of arc-disjoint time-respecting arborescences in temporal networks.     

Energy-efficient clustering in lossy wireless sensor networks

Recent experimental studies have revealed that a large percentage of wireless links are lossy and unreliable for data delivery in wireless sensor networks (WSNs). Such findings raise new challenges for the design of clustering algorithms in WSNs in terms of data reliability and energy efficiency. In this paper, we propose distributed clustering algorithms for lossy WSNs with a mobile collector, where the mobile collector moves close to each cluster head to receive data directly and then uploads collected data to the base station. We first consider constructing one-hop clusters in lossy WSNs where all cluster members are within the direct communication range of their cluster heads. We formulate the problem into an integer program, aiming at maximizing the network lifetime, which is defined as the number of rounds of data collection until the first node dies. We then prove that the problem is NP-hard. After that, we propose a metric-based distributed clustering algorithm to solve the problem. We adopt a metric called selection weight for each sensor node that indicates both link qualities around the node and its capability of being a cluster head. We further extend the algorithm to multi-hop clustering to achieve better scalability. We have found out that the performance of the one-hop clustering algorithm in small WSNs is very close to the optimal results obtained by mathematical tools. We have conducted extensive simulations for large WSNs and the results demonstrate that the proposed clustering algorithms can significantly improve the data reception ratio, reduce the total energy consumption in the network and prolong network lifetime compared to a typical distributed clustering algorithm, HEED, that does not consider lossy links.     

Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme

One of the most important issues in developing an evolutionary optimization algorithm is the proper handling of any constraints on the problem. One must balance the objective function against the degree of constraint violation in such a way that neither is dominant. Common approaches to strike this balance include implementing a penalty function and the more recent stochastic ranking method, but these methods require an extra tuning parameter which must be chosen by the user. The present paper demonstrates that a proper balance can be achieved using an addition of ranking method. Through the ranking of the individuals with respect to the objective function and constraint violation independently, we convert these two properties into numerical values of the same order of magnitude. This removes the requirement of a user-specified penalty coefficient or any other tuning parameters. Direct addition of the ranking terms is then performed to integrate all information into a single decision variable. This approach is incorporated into a (μ, λ) evolution strategy and tested on thirteen benchmark problems, one engineering design problem, and five difficult problems with a high dimensionality or many constraints. The performance of the proposed strategy is similar to that of the stochastic ranking method when dealing with inequality constraints, but it has a much simpler ranking procedure and does not require any tuning parameters. A percentage-based tolerance value adjustment scheme is also proposed to enable feasible search when dealing with equality constraints.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.     

Capturing an intruder in product networks

In this paper, we propose a solution to the problem of capturing an intruder in a product network. This solution is derived based on the assumption of existing algorithms for basic member graphs of a graph product. In this problem, a team of cleaner agents are responsible for capturing a hostile intruder in the network. While the agents can move in the network one hop at a time, the intruder is assumed to be arbitrarily fast in a way that it can traverse any number of nodes contiguously as far as no agents reside in those nodes. Here, we consider a version of the problem where each agent can replicate new agents. Thus, the algorithm starts with a single agent and new agents are created on demand. We propose a novel method for deriving intrusion capturing algorithms based on the abstract idea of spanning search trees. Later, we utilize this method for deriving capturing algorithms for Cartesian product graphs.     

Selecting the right MBA schools – An application of self-organizing map networks

The self-organizing map (SOM) network, an unsupervised neural computing network, is a categorization network developed by Kohonen. The SOM network was designed for solving problems that involve tasks such as clustering, visualization, and abstraction. In this study, we apply the clustering and visualization capabilities of SOM to group and plot the top 79 MBA schools as ranked by US News and World Report (USN&WR) into a two-dimensional map with four segments. The map should assist prospective students in searching for the MBA programs that best meet their personal requirements. Comparative analysis with the outputs from two popular clustering techniques K-means analysis and a two-step Factor analysis/K-means procedure are also included.     

On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

Common sets of weights as summaries of DEA profiles of weights: With an application to the ranking of professional tennis players

In this paper, we propose a DEA approach aimed at deriving a common set of weights (CSW) to be used to the ranking of decision making units (DMUs). The idea of this approach is to minimize the deviations of the CSW from the DEA profiles of weights without zeros of the efficient DMUs. This minimization reduces in particular the differences between the DEA profiles of weights that are chosen, so the CSW proposed is a representative summary of such DEA weights profiles. We use several norms to the measurement of such differences. As a result, the CSWs derived are actually different summaries of the chosen DEA profiles of weights like their average profile of their median profile. This approach is illustrated with an application to the ranking of professional tennis players.     

Improving search results with data mining in a thematic search engine

The problem of obtaining relevant results in web searching has been tackled with several approaches. Although very effective techniques are currently used by the most popular search engines when no a priori knowledge on the user's desires beside the search keywords is available, in different settings it is conceivable to design search methods that operate on a thematic database of web pages that refer to a common body of knowledge or to specific sets of users. We have considered such premises to design and develop a search method that deploys data mining and optimization techniques to provide a more significant and restricted set of pages as the final result of a user search. We adopt a vectorization method based on search context and user profile to apply clustering techniques that are then refined by a specially designed genetic algorithm. In this paper we describe the method, its implementation, the algorithms applied, and discuss some experiments that has been run on test sets of web pages.     

Structural reproduction of social networks in computer-mediated communication forums

This study explores the relationship between the structure of an existing social network and the structure of an emergent discussion-board network in an undergraduate university class. Thirty-one students were issued with laptop computers that remained in their possession for the duration of the semester. While using these machines, participants' email log files were collected directly from the University's email servers. The analysis compared structural attributes of actors evident in their social network with the emergent structural properties measured from interactions in a shared discussion board environment. A significant relationship was found between the existing social network structure and the emergent communication patterns, suggesting that existing relationships have a strong influence on subsequent computer-mediated communication. Additional matrices were used to control for gender, major and perceived computer efficacy, none of which had a significant effect.     

Business process mining: An industrial application

Contemporary information systems (e.g., WfM, ERP, CRM, SCM, and B2B systems) record business events in so-called event logs. Business process mining takes these logs to discover process, control, data, organizational, and social structures. Although many researchers are developing new and more powerful process mining techniques and software vendors are incorporating these in their software, few of the more advanced process mining techniques have been tested on real-life processes. This paper describes the application of process mining in one of the provincial offices of the Dutch National Public Works Department, responsible for the construction and maintenance of the road and water infrastructure. Using a variety of process mining techniques, we analyzed the processing of invoices sent by the various subcontractors and suppliers from three different perspectives: (1) the process perspective, (2) the organizational perspective, and (3) the case perspective. For this purpose, we used some of the tools developed in the context of the ProM framework. The goal of this paper is to demonstrate the applicability of process mining in general and our algorithms and tools in particular.     

Stochastic shortest path with unlimited hops

We present new results for the Stochastic Shortest Path problem when an unlimited number of hops may be used. Nodes and links in the network may be congested or uncongested, and their states change over time. The goal is to adaptively choose the next node to visit such that the expected cost to the destination is minimized. Since the state of a node may change, having the option to revisit a node can improve the expected cost. Therefore, the option to use an unbounded number of hops may be required to achieve the minimum expected cost. We show that when revisits are prohibited, the optimal routing problem is np-hard. We also prove properties about networks for which continual improvement may occur.We study the related routing problem which asks whether it is possible to determine the optimal next node based on the current node and state, when an unlimited number of hops is allowed. We show that as the number of hops increases, this problem may not converge to a solution.