Community search, which finds cohesive subgraphs containing given query vertices, has attracted much attention in decades. On attributed graphs, when considering the fairness of members' attributes in a community, the cohesiveness constraint of a clique is too strong, which often causes no fair clique based communities can be found. Thus, in this paper, we use the k-truss model, which is a relaxation of the clique but whose members have large engagement and high tie strength, to describe fair communities, namely fair k-truss communities (FTC) and anchored fair k-truss communities (AFTC, using anchored vertices to help satisfying the fairness constraint). We formulate the FTC and AFTC search problems to find the FTC or AFTC containing a given query vertex$q$which has the largest$k$and the smallest diameter. We prove the hardness of both problems. We develop several greedy algorithms and acceleration strategies to solve FTC and AFTC search problems. Experiments on 8 real-world networks show the significance of our FTC and AFTC models, and high performance of our algorithms and acceleration strategies.

Betweenness centrality (BC), a classic measure which quantifies the importance of a vertex to act as a communication "bridge" between other vertices in the network, is widely used in many practical applications. With the advent of large heterogeneous information networks (HINs) which contain multiple types of vertices and edges like movie or bibliographic networks, it is essential to study BC computation on HINs. However, existing works about BC mainly focus on homogeneous networks. In this paper, we are the first to study a specific type of vertices' BC on HINs, e.g., find which vertices with typeAare important bridges to the communication between other vertices also with typeA?We advocate a meta path-based BC framework on HINs and formalize both coarse-grained and fine-grained BC (cBC and fBC) measures under the framework. We propose a generalized basic algorithm which can apply to computing not only cBC and fBC but also their variants in more complex cases. We develop several optimization strategies to speed up cBC or fBC computation by network compression and breadth-first search directed acyclic graph (BFS DAG) sharing. Experiments on several real-world HINs show the significance of cBC and fBC, and the effectiveness of our proposed optimization strategies.

Analyzing dynamic information networks, which contain evolving objects and links, to meet users various needs has attracted much attention in recent years. For sales companies, recruiting staff who are socialites would help to increase sales volume since such staff often sell more. For universities, employing active collaborators who are productive and well connected to many different scholars over time could bring many benefits to their development. However, no previous work has focused on the discovery of socialites and active collaborators who are worthy of investment in reality. In this paper, we advocate a new concept of attractive individuals to model such special objects. We also introduce the concept of attractive groups to represent groups of well-connected attractive individuals. We analyze the complexity of the attractive individual and group search problems. A time and space efficient algorithm is presented to detect attractive individuals. Furthermore, three algorithms are respectively proposed to find top-k representative attractive groups. Experiments on 6 real-world datasets show high performance of our methods and the significance of attractive individuals and groups in reality.

Analyzing dynamic information networks, which contain evolving objects and links, has attracted much attention in recent years. For sales companies, recruiting staff who are socialites would help to increase sales volume since such staff often sell more. For universities, employing active collaborators who are productive and well connected to many different scholars over time could bring many benefits to their development. However, no previous work has focused on socialites and active collaborators who are worthy of investment in reality. In this paper, we advocate attractive individuals to model such special objects, and introduce attractive groups to represent groups of well-connected attractive individuals. Then we propose several algorithms to search attractive individuals and groups. Extensive experiments show high performance of our methods and the significance of attractive individuals and groups in reality.