# Efficient Rational Community Detection in Attribute Bipartite Graphs

Authors: Chen Yang; Hao Ji; Yanping Wu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Bipartite graph is widely used to model the complex relationships among two types of entities. Community detection (CD) is a fundamental tool for graph analysis, which aims to find all or top-k densely connected subgraphs. However, the existing studies about the CD problem usually focus on structure cohesiveness, such as α,β-core, but ignore the attributes within the relationships, which can be modeled as attribute bipartite graphs. Moreover, the returned results usually suffer from rationality issues. To overcome the limitations, in this paper, we introduce a novel metric, named rational score, which takes both preference consistency and community size into consideration to evaluate the community. Based on the proposed rational score and the widely used α,β-core model, we propose and investigate the rational α,β-core detection in attribute bipartite graphs (RCD-ABG), which aims to retrieve the connected α,β-core with the largest rational score. We prove that the problem is NP-hard and the object function is nonmonotonic and non-submodular. To tackle RCD-ABG problem, a basic greedy framework is first proposed. To further improve the quality of returned results, two optimized strategies are further developed. Finally, extensive experiments are conducted on 6 real-world bipartite networks to evaluate the performance of the proposed model and techniques. As shown in experiments, the returned community is significantly better than the result returned by the traditional α,β-core model.


---

## Body

## 1. Introduction

A bipartite graph is composed of two disjoint vertex sets, and there are only edges connecting vertices from different sets. Due to its proliferation applications like fraudsters detection [1] and collaboration group maintenance [2], many fundamental problems have been investigated to analyze the bipartite graphs. Among these problems, community detection (CD) aims to find all or top-k communities by leveraging different models like α,β-core [3], bitruss [4], and so on. Due to its unique feature, the α,β-core model is widely adopted in different domains. Given a bipartite graph, the α,β-core is the maximal subgraph where the degree of each vertex in the upper layer is at least α and the degree of each vertex in the lower layer is at least β. Nonetheless, previous models mainly focus on the cohesiveness structure of the graphs but neglect the attribute properties with community.In real applications, the relationships between different entities often have certain characteristics, which can be modeled as attribute bipartite graphs. For example, in the user-movie network of Figure1, the upper layer denotes a set of users and the lower layer are the set of movies. Each edge is associated with a number denoting the score assigned from a user to a movie. For a discussion group in the platform, it will have a more harmonious atmosphere if users have high consistency of preference (e.g., rating the same score or tag for the same movie). Besides, small discussion group is more conducive to frequent communication among users. However, the existing research cannot capture those properties. Motivated by this, in this paper, we introduce a novel metric, named rational score, which takes both preference consistency and community size into consideration to evaluate a community. Furthermore, we formally define the problem of rational community detection over attribute bipartite graphs (RCD-ABG), which attempts to find the connected α,β-core with the largest rational score. The following is a motivation example.Figure 1
A user-movie network.Example 1.
Reconsider the user-movie network in Figure1, where the number on the edge denotes the corresponding rating for the movie. Note that the scoring mechanism adopts a five-point system, so the score varies from 1 to 5 in the network. Suppose α = 2 and β = 2 here. Based on the definition, the subgraph induced by vertex set u2,u3,…,u8,v2,v3,…,v8 is a 2,2-core, where the degree of each vertex is at least 2. However, in the 2,2-core, many users have distinct scoring schemes for the same movie. For example, users u6, u7, and u8 gave three different scores to the movie v7. Moreover, the community size is too large to facilitate communication between users. For instance, users u2 and u6 even have not watched the same movie ever. Given α = 2 and β = 2, the vertices in the orange rectangle are our identified rational α,β-core community. Note that, due to the complex equation involved, the detailed definition of rational α,β-core community can be found in preliminaries section. As we can observe, in this community, most users share the same movie taste and the number of people in the group is more reasonable.


### 1.1. Applications

The RCD-ABG problem can find many real-world applications. We list some examples as follows.(i)
Discussion Group Mining. In some real-world bipartite graphs such as BookCrossing, edges denote rating relationships between users and books. There are many discussion groups with these platforms. For users, they are more likely to stay active in a discussion group if the users inside share the same taste. Besides, users will prefer to discuss different topics in a group with appropriate size. This is because too many users can make them uncomfortable and too few will make the discussion difficult to carry on. Hence, by retrieving the rational group, the platform can provide group recommendation more precisely, which is helpful for better user experience.(ii)
Personalized Product Recommendation. In customer-movie bipartite networks, the customers will rate the movies based on their personal preference and movie performance. By retrieving the rational α,β-core, the personalized movie recommendation can be provided to customers in the rational community. For instance, in the community found in the orange rectangle in Figure 1, the platform can recommend movie v4 for user u2. This is because v4 is given the common score from other customers (i.e., u3 and u4). Similarly, movie v2 can be recommended for user u4.


### 1.2. Challenges

To our best knowledge, we are the first to investigate the rationalα,β-core detection problem in attribute bipartite graphs. We prove the problem is NP-hard and we adopt the greedy framework to remove the best vertex iteratively. However, removing a vertex from the graph may make many other vertices drop from the result, which limits the effectiveness of the algorithm. Hence, it is necessary to develop optimized techniques to address these challenges.


### 1.3. Our Solution

Due to the NP-hardness of the problem, a basic greedy framework is proposed by adopting the greedy framework. In general, we remove the vertex with the smallest marginal gain at each iteration and calculate the remainingα,β-core with its rational score. We stop this process until there is no α,β-core and return the α,β-core with the largest rational score as the result. To address the discussed drawbacks of our basic greedy framework, we further develop two improved strategies, namely, 2-hop neighbors-based optimization and followers-based optimization. Specifically, in 2-hop neighbors-based optimization, we approximate the marginal score by considering the 2-hop neighbors of the removed vertex in the same layer. In our followers-based optimization, we consider the followers of the removed vertex and modify the marginal rational score.


### 1.4. Contributions

The contributions of this paper are summarized as follows.(i)
To better capture the properties within bipartite graph community, we conduct the first research to propose and investigate the rational community detection problem over attribute bipartite graphs by leveraging the novel rational score metric developed.(ii)
Theoretically, we prove that the problem is NP-hard, and the rational score function is nonmonotonic and non-submodular.(iii)
The basic greedy framework is first presented. To further improve the quality of returned results, two optimized strategies are proposed, namely, 2-hop neighbors-based optimization and followers-based optimization.(iv)
Experiments over 6 real-world bipartite graphs are conducted to show the superiority of proposed techniques. Compared with the traditionalα,β-core model, our model is much more effective.


### 1.5. Roadmap

We organize the rest of this paper as follows. We first review the related work. Then, we introduce the problem investigated and the corresponding problem properties. Next, we will present the basic greedy framework and two optimized strategies. Finally, we report the performance of our algorithms over real datasets and conclude the paper.


## 1.1. Applications

The RCD-ABG problem can find many real-world applications. We list some examples as follows.(i)
Discussion Group Mining. In some real-world bipartite graphs such as BookCrossing, edges denote rating relationships between users and books. There are many discussion groups with these platforms. For users, they are more likely to stay active in a discussion group if the users inside share the same taste. Besides, users will prefer to discuss different topics in a group with appropriate size. This is because too many users can make them uncomfortable and too few will make the discussion difficult to carry on. Hence, by retrieving the rational group, the platform can provide group recommendation more precisely, which is helpful for better user experience.(ii)
Personalized Product Recommendation. In customer-movie bipartite networks, the customers will rate the movies based on their personal preference and movie performance. By retrieving the rational α,β-core, the personalized movie recommendation can be provided to customers in the rational community. For instance, in the community found in the orange rectangle in Figure 1, the platform can recommend movie v4 for user u2. This is because v4 is given the common score from other customers (i.e., u3 and u4). Similarly, movie v2 can be recommended for user u4.


## 1.2. Challenges

To our best knowledge, we are the first to investigate the rationalα,β-core detection problem in attribute bipartite graphs. We prove the problem is NP-hard and we adopt the greedy framework to remove the best vertex iteratively. However, removing a vertex from the graph may make many other vertices drop from the result, which limits the effectiveness of the algorithm. Hence, it is necessary to develop optimized techniques to address these challenges.


## 1.3. Our Solution

Due to the NP-hardness of the problem, a basic greedy framework is proposed by adopting the greedy framework. In general, we remove the vertex with the smallest marginal gain at each iteration and calculate the remainingα,β-core with its rational score. We stop this process until there is no α,β-core and return the α,β-core with the largest rational score as the result. To address the discussed drawbacks of our basic greedy framework, we further develop two improved strategies, namely, 2-hop neighbors-based optimization and followers-based optimization. Specifically, in 2-hop neighbors-based optimization, we approximate the marginal score by considering the 2-hop neighbors of the removed vertex in the same layer. In our followers-based optimization, we consider the followers of the removed vertex and modify the marginal rational score.


## 1.4. Contributions

The contributions of this paper are summarized as follows.(i)
To better capture the properties within bipartite graph community, we conduct the first research to propose and investigate the rational community detection problem over attribute bipartite graphs by leveraging the novel rational score metric developed.(ii)
Theoretically, we prove that the problem is NP-hard, and the rational score function is nonmonotonic and non-submodular.(iii)
The basic greedy framework is first presented. To further improve the quality of returned results, two optimized strategies are proposed, namely, 2-hop neighbors-based optimization and followers-based optimization.(iv)
Experiments over 6 real-world bipartite graphs are conducted to show the superiority of proposed techniques. Compared with the traditionalα,β-core model, our model is much more effective.


## 1.5. Roadmap

We organize the rest of this paper as follows. We first review the related work. Then, we introduce the problem investigated and the corresponding problem properties. Next, we will present the basic greedy framework and two optimized strategies. Finally, we report the performance of our algorithms over real datasets and conclude the paper.


## 2. Related Work

In this paper, we conduct the first attempt to propose and investigate the rationalα,β-core problem. Thus, we will present the related work from the following two aspects.Cohesive Subgraphs Mining. In different domains, graphs are widely used to model the complex relationships among different entities. As a key problem in graph analysis, community search has been widely studied in the literature and different models have been proposed to measure the cohesiveness of community, such as k-core, k-truss, and clique. In many real-world applications, both graph structures and attribute information are considered. For attribute graph processing, community search problem used both link relationship and attributes because the attributes usually can make communities more meaningful and easy to interpret [5]. In [5], Fang et al. proposed attributed community query (or ACQ) problem, which returned an attributed community (AC) for an attributed graph. The returned community should satisfy both structure cohesiveness constraint and keyword cohesiveness constraint. In [6], Huang and Lakshmanan considered communities based on topics of interest and proposed attributed truss communities (ATC) search problem. They aimed to find connected k-truss subgraphs that contained query vertices with the largest attribute relevance score. In [7], Zhang et al. proposed a keyword-centric community search (KCCS) problem over attribute graphs. They tried to find a community, where the degree of each vertex should be at least k, and the distance between the vertex and all query keywords is minimized. Influential community search has also been studied in [8], where each vertex is associated with a number denoting its influence. Its goal was to find communities with the largest influence.Bipartite Graph Analysis. Recently, the bipartite graph has attracted much attention due to its proliferate applications like online group recommendation and fraudsters’ detection [2]. In [9], Borgatti and Everett were the first to investigate the cohesive communities in bipartite graphs for network analysis. To analyze the properties of bipartite networks, numerous models have been investigated, such as α,β-core [10], bitruss [11], and biclique [12]. In [13], the significant α,β-community search problem was proposed and studied on weighted bipartite graphs, where each edge is associated with a weight. They aimed to find the significant α,β-community that contained query vertex and maximized the minimum edge weight within community. In [4], Wang et al. studied the bitruss model in bipartite graphs. Given a bipartite graph, the bitruss is the maximal subgraph where each edge is contained in at least k butterflies. In the literature, considering the fairness constraints, the fair clustering problems [14–16] were investigated to find communities on bipartite graphs. However, none of the previous studies take the rationality of communities into consideration.


## 3. Preliminaries

In this section, we first introduce some necessary concepts and present the formal definition of the rational community detection problem over attribute bipartite graphs. Table1 summarizes the notations that are frequently used in this paper.Table 1
Summary of notations.
NotationDefinitionG=U,L,E,AAn attribute bipartite graphU/LThe vertex setEThe edge setA=a1,…,atThe attribute set of edgesS=US,LS,ES,ASAn induced subgraph ofGnNumber of vertices inGmNumber of edges inGu,vVertex inGNSuThe set ofu’s neighbors in SdSuThe degree ofu in Sα,βThe degree constraintxGvConsensus score of vertexv∈LxSConsensus score of subgraphSfSRational score of subgraphS


### 3.1. Problem Definition

We consider an attribute bipartite graphG=U,L,E,A as an undirected graph without multiple edges and self-loops. U and L are the two disjoint and independent vertex sets in G; that is, U∩L=∅. E is the edge set and each edge e=u,v∈E connects one vertex u∈U and one vertex v∈L; that is, E⊆U×L. A=a1,a2,…,at is the attribute set. Each edge e∈E is associated with an attribute (e.g., number/tag) ae∈A. We use n and m to denote the number of vertices and edges in G, respectively. Given an attribute bipartite graph G, a subgraph S=US,LS,ES,AS is an induced subgraph of G; if US⊆U, LS⊆L, ES=E∩US×LS and AS⊆A. For a vertex u∈S, the set of u’s neighbors is denoted by NSu (i.e., the adjacent vertices of u). dSu=NSu denotes the degree of u in S (i.e., the number of u’s neighbor vertices).Definition 1.
(α,β-core). Given a bipartite graph G, a subgraph S is the α,β-core of G, denoted by Cα,β, if it satisfies the following: (1) degree constraint (i.e., dSu≥α for each vertex u∈US and dSv≥β for each vertex v∈LS); (2​S is maximal; that is, any supergraph S′⊃S is not a α,β-core.
To compute theα,β-core, in our paper, we iteratively remove the vertices in two layers violating the corresponding degree constraint until there are no unsatisfied vertices in the graph, the details of which are shown in Algorithm 1. The time complexity is Om [17]. As discussed before, the people in a rational discussion group are cohesive and have consistent preference. In the following, we first introduce the consensus score of vertex and community, respectively. Note that we only consider the consensus score of the vertex in lower (e.g., movie) layer. The rational α,β-core model is further developed based on the rational score consisting of the consensus score and community size. Then, we present the formal definition of our problem.
Algorithm 1: Compute α,β-core.
Input:G: a bipartite graph, α, β: degree constraintsOutput: The α,β-core of G(1)
While exists u∈U with du<α or u∈V with du<βdo(2)
G⟵G/u(3)
returnGDefinition 2.
(Consensus score). Given an attribute bipartite graphG, the consensus score of each vertex v∈L, denoted by xGv/dGv, where xGv is the maximum number of its adjacent edges in G with the same attribute number. For a subgraph S of G, its consensus score is defined as xS=∑v∈LSxSv/dSv/LS, where ∑v∈LSxSv/dSv is the sum of consensus score of all vertices in LS and LS is the number of vertices in the lower layer of S.Example 2.
Considering the vertices in the orange line of the bipartite graph in Figure1, the consensus score of v3 is 2/3. The consensus score of community in the orange line is 8/9.
To judge a community, we not only want to consider the consensus but also want to consider the size constraint of it. This is because that the traditional study group with not very large size can facilitate people there to discuss and analyze problem. So, we also combine the size constraint into our rational score function, which is expressed as follows:(1)fS=λ∑v∈LSxSv/dSvLS+1−λ1USLS,where λ is a parameter to make the trade-off between the consensus score and the community size. Based on this rational score function, we give the definition of rational community.Definition 3.
(rationalα,β-core). Given an attribute bipartite graph G and two positive integers α and β, a subgraph S is a attribute α,β-core of G, denoted by RCα,β, if it meets the following three criteria:(i)
Connectivity:S is connected(ii)
Cohesiveness:S is a α,β-core(iii)
Rationality:S has the largest rational score fS among subgraphs satisfying the above criteria


#### 3.1.1. Problem Statement

Given an attribute bipartite graphG and two positive integers α and β, we aim to develop efficient algorithms to find the rational α,β-core (i.e., the α,β-core with the largest rational score).


### 3.2. Problem Properties

As shown in Theorem1, the problem studied is NP-hard. Besides, the rational score function is nonmonotonic and non-submodular, whose details are in Theorem 2.Theorem 1.
Given an attribute bipartite graphG, the problem of computing the rational α,β-core is NP-hard.Proof.
Whenα>0 and β>0, we reduce the biclique problem [17] to RCD-ABG problem. Given an attribute bipartite graph G=V=U∪L,E,A, where for each vertex in lower layer L, its adjacent edges have distinct attribute. This means that given a subgraph S of G, the consensus score of each vertex v in LS is 1/dSv. Hence, our score function is converted to fS=λ∑v∈LS1/dSv/LS+1−λ1/USLS. In order to make the rational score large, for the first term of function, namely, λ∑v∈LS1/dSv/LS, we need to make the numerator be largest and the denominator be smallest. Due to the degree constraint of lower layer, the lower bound of dSv is β. So, the rational score function is f=λLS1/β/LS+1−λ1/USLS=λ1/β+1−λ1/USLS. Given the parameter α, β, and λ, to find rational α,β-core with largest f, US and LS need to be minimized, which means that US and LS should be equal to β and α, respectively. As discussed, each vertex u∈US (resp. u∈LS) should satisfy dSu≥α (resp. dSu≥β). This is a biclique that each vertex in different layers is connect, which is NP-hard [17]. Therefore, our problem is NP-hard. □Theorem 2.
The objective score functionfS is nonmonotonic and non-submodular.Proof.
Nonmonotonic. By considering the example in Figure 1, we first prove its nonmonotonicity. Note that we only keep two decimal places in the following. Suppose λ=0.5; we can see that in subgraph denoted by solid line, that is, S=u2,u3,u4,v2,v3,v4, fS = 0.5. After deleting vertex u2, fS/u2 = 0.53. While, by further deleting vertex u4, the present score is fS\u2\v2 = 0.5. Therefore, the function is nonmonotonic.
Non-Submodular. Given two sets A and B, fx is submodular if fA∪B+fA∩B≤fA+fB. We show the inequality does not hold by a counterexample in Figure 1. Suppose A = u2,u3,v2,v3 and B = u3,u4,v3,v4. We have fA = 0.5, fB = 0.5, fA∪B = 0.5, and fA∩B = 0.75. Thus, the equation does not hold and f is not submodular.


## 3.1. Problem Definition

We consider an attribute bipartite graphG=U,L,E,A as an undirected graph without multiple edges and self-loops. U and L are the two disjoint and independent vertex sets in G; that is, U∩L=∅. E is the edge set and each edge e=u,v∈E connects one vertex u∈U and one vertex v∈L; that is, E⊆U×L. A=a1,a2,…,at is the attribute set. Each edge e∈E is associated with an attribute (e.g., number/tag) ae∈A. We use n and m to denote the number of vertices and edges in G, respectively. Given an attribute bipartite graph G, a subgraph S=US,LS,ES,AS is an induced subgraph of G; if US⊆U, LS⊆L, ES=E∩US×LS and AS⊆A. For a vertex u∈S, the set of u’s neighbors is denoted by NSu (i.e., the adjacent vertices of u). dSu=NSu denotes the degree of u in S (i.e., the number of u’s neighbor vertices).Definition 1.
(α,β-core). Given a bipartite graph G, a subgraph S is the α,β-core of G, denoted by Cα,β, if it satisfies the following: (1) degree constraint (i.e., dSu≥α for each vertex u∈US and dSv≥β for each vertex v∈LS); (2​S is maximal; that is, any supergraph S′⊃S is not a α,β-core.
To compute theα,β-core, in our paper, we iteratively remove the vertices in two layers violating the corresponding degree constraint until there are no unsatisfied vertices in the graph, the details of which are shown in Algorithm 1. The time complexity is Om [17]. As discussed before, the people in a rational discussion group are cohesive and have consistent preference. In the following, we first introduce the consensus score of vertex and community, respectively. Note that we only consider the consensus score of the vertex in lower (e.g., movie) layer. The rational α,β-core model is further developed based on the rational score consisting of the consensus score and community size. Then, we present the formal definition of our problem.
Algorithm 1: Compute α,β-core.
Input:G: a bipartite graph, α, β: degree constraintsOutput: The α,β-core of G(1)
While exists u∈U with du<α or u∈V with du<βdo(2)
G⟵G/u(3)
returnGDefinition 2.
(Consensus score). Given an attribute bipartite graphG, the consensus score of each vertex v∈L, denoted by xGv/dGv, where xGv is the maximum number of its adjacent edges in G with the same attribute number. For a subgraph S of G, its consensus score is defined as xS=∑v∈LSxSv/dSv/LS, where ∑v∈LSxSv/dSv is the sum of consensus score of all vertices in LS and LS is the number of vertices in the lower layer of S.Example 2.
Considering the vertices in the orange line of the bipartite graph in Figure1, the consensus score of v3 is 2/3. The consensus score of community in the orange line is 8/9.
To judge a community, we not only want to consider the consensus but also want to consider the size constraint of it. This is because that the traditional study group with not very large size can facilitate people there to discuss and analyze problem. So, we also combine the size constraint into our rational score function, which is expressed as follows:(1)fS=λ∑v∈LSxSv/dSvLS+1−λ1USLS,where λ is a parameter to make the trade-off between the consensus score and the community size. Based on this rational score function, we give the definition of rational community.Definition 3.
(rationalα,β-core). Given an attribute bipartite graph G and two positive integers α and β, a subgraph S is a attribute α,β-core of G, denoted by RCα,β, if it meets the following three criteria:(i)
Connectivity:S is connected(ii)
Cohesiveness:S is a α,β-core(iii)
Rationality:S has the largest rational score fS among subgraphs satisfying the above criteria


### 3.1.1. Problem Statement

Given an attribute bipartite graphG and two positive integers α and β, we aim to develop efficient algorithms to find the rational α,β-core (i.e., the α,β-core with the largest rational score).


## 3.1.1. Problem Statement

Given an attribute bipartite graphG and two positive integers α and β, we aim to develop efficient algorithms to find the rational α,β-core (i.e., the α,β-core with the largest rational score).


## 3.2. Problem Properties

As shown in Theorem1, the problem studied is NP-hard. Besides, the rational score function is nonmonotonic and non-submodular, whose details are in Theorem 2.Theorem 1.
Given an attribute bipartite graphG, the problem of computing the rational α,β-core is NP-hard.Proof.
Whenα>0 and β>0, we reduce the biclique problem [17] to RCD-ABG problem. Given an attribute bipartite graph G=V=U∪L,E,A, where for each vertex in lower layer L, its adjacent edges have distinct attribute. This means that given a subgraph S of G, the consensus score of each vertex v in LS is 1/dSv. Hence, our score function is converted to fS=λ∑v∈LS1/dSv/LS+1−λ1/USLS. In order to make the rational score large, for the first term of function, namely, λ∑v∈LS1/dSv/LS, we need to make the numerator be largest and the denominator be smallest. Due to the degree constraint of lower layer, the lower bound of dSv is β. So, the rational score function is f=λLS1/β/LS+1−λ1/USLS=λ1/β+1−λ1/USLS. Given the parameter α, β, and λ, to find rational α,β-core with largest f, US and LS need to be minimized, which means that US and LS should be equal to β and α, respectively. As discussed, each vertex u∈US (resp. u∈LS) should satisfy dSu≥α (resp. dSu≥β). This is a biclique that each vertex in different layers is connect, which is NP-hard [17]. Therefore, our problem is NP-hard. □Theorem 2.
The objective score functionfS is nonmonotonic and non-submodular.Proof.
Nonmonotonic. By considering the example in Figure 1, we first prove its nonmonotonicity. Note that we only keep two decimal places in the following. Suppose λ=0.5; we can see that in subgraph denoted by solid line, that is, S=u2,u3,u4,v2,v3,v4, fS = 0.5. After deleting vertex u2, fS/u2 = 0.53. While, by further deleting vertex u4, the present score is fS\u2\v2 = 0.5. Therefore, the function is nonmonotonic.
Non-Submodular. Given two sets A and B, fx is submodular if fA∪B+fA∩B≤fA+fB. We show the inequality does not hold by a counterexample in Figure 1. Suppose A = u2,u3,v2,v3 and B = u3,u4,v3,v4. We have fA = 0.5, fB = 0.5, fA∪B = 0.5, and fA∩B = 0.75. Thus, the equation does not hold and f is not submodular.


## 4. Solution

In this section, a greedy framework is firstly developed to find the result, which is based on the concept of score function and marginal gain that we define. Considering the limitations of the basic method, we further propose two novel strategies with better quality.


### 4.1. A Basic Greedy Framework (BGF)

Intuitively, to find theα,β-core with largest score, we can delete those vertices whose deletion will increase the score. Based on this, we present our basic greedy framework by introducing the rational marginal gain as follows.Definition 4.
(rational marginal score). Given an attribute bipartite graphG and a vertex u∈G, the rational marginal gain is defined as(2)△Gu=fG−fGNG′u∪uu∈U.fG−fGuu∈L,where NG′u is the set of u’s neighbors in L that violate the degree constraint after removing vertex u.


#### 4.1.1. The Basic Greedy Framework (BGF)

The details of BGF are illustrated in Algorithm 2, which includes three main steps. We useG to denote the set of all connected α,β-cores. Step1. We find all α,β-cores of G and store them into G in Line 2. We use Gi to denote the current processing α,β-core. Step2. At each iteration, we greedily peel the vertex v in graph Gi providing the smallest marginal gain △Giv=fGi−fGi/v (Line 5), which is called the best vertex. After removing best vertex, we calculate the α,β-core in the remaining graph. If there are many connected α,β-cores, we push back them into G (Lines 6–8). We continue this process until there is no α,β-core in the graph. Note that the rational marginal gain may be a negative number, which means the score of function increase. Step3. We output the result with the largest score among obtained attribute α,β-cores (Line 9).Algorithm 2: A basic greedy framework (BGF).
Input:G: attribute bipartite graph, α: degree constraint in upper layer, β: degree constraint in lower layerOutput:H: the connected α,β-core with the largest rational score(1)
i⟵1(2)
G⟵ an empty vector//Step 1(3)
G⟵ all connected Cα,βG//Step 2(4)
While:G≠∅do(5)
u⟵argminv∈Gi△Giv(6)
for each connected Cα,βGi/u in Gi\udo(7)
push backCα,βGi/u into G(8)
i⟵i+1;//Step 3(9)
H⟵argG′G′∈GfG′;Example 3.
Considering the user-movie network in Figure1. Suppose α  = 2, β  = 2. According the BGF, vertex v6 is removed firstly and the rational score of the remained 2,2-core is 0.415476. Similarly, we remove vertices v7, v4, and v3, iteratively. The corresponding rational score is 0.481667, 0.6, and 0. Therefore, the returned result is u2,u3,v2,v3 with rational score of 0.6.


### 4.2. Optimized Strategies

The basic greedy framework is simple but suffers from the following drawback. When removing a vertexv from the subgraph S, it may make the support of some other vertices decrease and lead them to drop from the community in succession. Note that these vertices are called the followers of v including v itself, denoted as ℱSv. If the removal vertex has a large number of followers, it can severely limit the effectiveness of the algorithm. Hence, we need to consider the effect of each removal vertex. In the following section, we propose two improved strategies to handle the limitation.


#### 4.2.1. 2-Hop Neighbors Optimization (OS-I)

As observed, if the removal vertex is in the lower layer, its 2-hop neighbors in the same layer may violate the degree constraint and be deleted, which significantly affect the rational score. Based on this, we use the following equation to approximate marginal score function△Gu by △^Gu,(3)△^Gu=fG−fGNG′u∪uu∈U,fG−fGH2Gu∪u,where H2Gv is the 2-hop neighbors of v in the lower layer. Therefore, the best vertex is adjusted as u⟵argminv∈Gi△^Giv in Line 5 of algorithm 1 and other steps are the same.Example 4.
Reconsider the user-movie network in Figure1. Suppose α = 2, β = 2. According to the OS-I, we remove vertex v7 firstly and obtain the rational score of the remained 2,2-core. Then, we remove u6 and obtain the corresponding score of 0.6556. After removing u3, the obtained score is 0. So, we return the result by u2,u3,u4,v2,v3,v4 with a score of 0.6556.


#### 4.2.2. Followers-Based Optimization (OS-II)

The second idea is motivated by the followers of each removal vertex. Generally, instead of removing one vertex and calculating the rational marginal gain, we remove a vertex with its all followers from the current candidate graph that have the smallest attribute marginal gain. Hence, the marginal score is modified as the following equation:(4)△˜Gu=fG−fGℱGu,and the other steps are the same as BGF.Example 5.
Reconsider the example in Figure1. Suppose α = 2, β = 2. According to the OS-II, vertex u7 is removed firstly and the obtained score is 0.455333. Then, we remove v5 and calculate the score with 0.65556. After deleting u2, the score is 0. Therefore, we return the result u2,u3,u4,v2,v3,v4 with a score of 0.65556.


#### 4.2.3. Analysis

The main difference between BGF and optimized algorithm is the best vertex. In BGF, calculating the marginal score of a vertex isO1 time. In OS-II, the time complexity of identifying the followers of the vertex is Om, which may significantly increase the running time.


## 4.1. A Basic Greedy Framework (BGF)

Intuitively, to find theα,β-core with largest score, we can delete those vertices whose deletion will increase the score. Based on this, we present our basic greedy framework by introducing the rational marginal gain as follows.Definition 4.
(rational marginal score). Given an attribute bipartite graphG and a vertex u∈G, the rational marginal gain is defined as(2)△Gu=fG−fGNG′u∪uu∈U.fG−fGuu∈L,where NG′u is the set of u’s neighbors in L that violate the degree constraint after removing vertex u.


### 4.1.1. The Basic Greedy Framework (BGF)

The details of BGF are illustrated in Algorithm 2, which includes three main steps. We useG to denote the set of all connected α,β-cores. Step1. We find all α,β-cores of G and store them into G in Line 2. We use Gi to denote the current processing α,β-core. Step2. At each iteration, we greedily peel the vertex v in graph Gi providing the smallest marginal gain △Giv=fGi−fGi/v (Line 5), which is called the best vertex. After removing best vertex, we calculate the α,β-core in the remaining graph. If there are many connected α,β-cores, we push back them into G (Lines 6–8). We continue this process until there is no α,β-core in the graph. Note that the rational marginal gain may be a negative number, which means the score of function increase. Step3. We output the result with the largest score among obtained attribute α,β-cores (Line 9).Algorithm 2: A basic greedy framework (BGF).
Input:G: attribute bipartite graph, α: degree constraint in upper layer, β: degree constraint in lower layerOutput:H: the connected α,β-core with the largest rational score(1)
i⟵1(2)
G⟵ an empty vector//Step 1(3)
G⟵ all connected Cα,βG//Step 2(4)
While:G≠∅do(5)
u⟵argminv∈Gi△Giv(6)
for each connected Cα,βGi/u in Gi\udo(7)
push backCα,βGi/u into G(8)
i⟵i+1;//Step 3(9)
H⟵argG′G′∈GfG′;Example 3.
Considering the user-movie network in Figure1. Suppose α  = 2, β  = 2. According the BGF, vertex v6 is removed firstly and the rational score of the remained 2,2-core is 0.415476. Similarly, we remove vertices v7, v4, and v3, iteratively. The corresponding rational score is 0.481667, 0.6, and 0. Therefore, the returned result is u2,u3,v2,v3 with rational score of 0.6.


## 4.1.1. The Basic Greedy Framework (BGF)

The details of BGF are illustrated in Algorithm 2, which includes three main steps. We useG to denote the set of all connected α,β-cores. Step1. We find all α,β-cores of G and store them into G in Line 2. We use Gi to denote the current processing α,β-core. Step2. At each iteration, we greedily peel the vertex v in graph Gi providing the smallest marginal gain △Giv=fGi−fGi/v (Line 5), which is called the best vertex. After removing best vertex, we calculate the α,β-core in the remaining graph. If there are many connected α,β-cores, we push back them into G (Lines 6–8). We continue this process until there is no α,β-core in the graph. Note that the rational marginal gain may be a negative number, which means the score of function increase. Step3. We output the result with the largest score among obtained attribute α,β-cores (Line 9).Algorithm 2: A basic greedy framework (BGF).
Input:G: attribute bipartite graph, α: degree constraint in upper layer, β: degree constraint in lower layerOutput:H: the connected α,β-core with the largest rational score(1)
i⟵1(2)
G⟵ an empty vector//Step 1(3)
G⟵ all connected Cα,βG//Step 2(4)
While:G≠∅do(5)
u⟵argminv∈Gi△Giv(6)
for each connected Cα,βGi/u in Gi\udo(7)
push backCα,βGi/u into G(8)
i⟵i+1;//Step 3(9)
H⟵argG′G′∈GfG′;Example 3.
Considering the user-movie network in Figure1. Suppose α  = 2, β  = 2. According the BGF, vertex v6 is removed firstly and the rational score of the remained 2,2-core is 0.415476. Similarly, we remove vertices v7, v4, and v3, iteratively. The corresponding rational score is 0.481667, 0.6, and 0. Therefore, the returned result is u2,u3,v2,v3 with rational score of 0.6.


## 4.2. Optimized Strategies

The basic greedy framework is simple but suffers from the following drawback. When removing a vertexv from the subgraph S, it may make the support of some other vertices decrease and lead them to drop from the community in succession. Note that these vertices are called the followers of v including v itself, denoted as ℱSv. If the removal vertex has a large number of followers, it can severely limit the effectiveness of the algorithm. Hence, we need to consider the effect of each removal vertex. In the following section, we propose two improved strategies to handle the limitation.


### 4.2.1. 2-Hop Neighbors Optimization (OS-I)

As observed, if the removal vertex is in the lower layer, its 2-hop neighbors in the same layer may violate the degree constraint and be deleted, which significantly affect the rational score. Based on this, we use the following equation to approximate marginal score function△Gu by △^Gu,(3)△^Gu=fG−fGNG′u∪uu∈U,fG−fGH2Gu∪u,where H2Gv is the 2-hop neighbors of v in the lower layer. Therefore, the best vertex is adjusted as u⟵argminv∈Gi△^Giv in Line 5 of algorithm 1 and other steps are the same.Example 4.
Reconsider the user-movie network in Figure1. Suppose α = 2, β = 2. According to the OS-I, we remove vertex v7 firstly and obtain the rational score of the remained 2,2-core. Then, we remove u6 and obtain the corresponding score of 0.6556. After removing u3, the obtained score is 0. So, we return the result by u2,u3,u4,v2,v3,v4 with a score of 0.6556.


### 4.2.2. Followers-Based Optimization (OS-II)

The second idea is motivated by the followers of each removal vertex. Generally, instead of removing one vertex and calculating the rational marginal gain, we remove a vertex with its all followers from the current candidate graph that have the smallest attribute marginal gain. Hence, the marginal score is modified as the following equation:(4)△˜Gu=fG−fGℱGu,and the other steps are the same as BGF.Example 5.
Reconsider the example in Figure1. Suppose α = 2, β = 2. According to the OS-II, vertex u7 is removed firstly and the obtained score is 0.455333. Then, we remove v5 and calculate the score with 0.65556. After deleting u2, the score is 0. Therefore, we return the result u2,u3,u4,v2,v3,v4 with a score of 0.65556.


### 4.2.3. Analysis

The main difference between BGF and optimized algorithm is the best vertex. In BGF, calculating the marginal score of a vertex isO1 time. In OS-II, the time complexity of identifying the followers of the vertex is Om, which may significantly increase the running time.


## 4.2.1. 2-Hop Neighbors Optimization (OS-I)

As observed, if the removal vertex is in the lower layer, its 2-hop neighbors in the same layer may violate the degree constraint and be deleted, which significantly affect the rational score. Based on this, we use the following equation to approximate marginal score function△Gu by △^Gu,(3)△^Gu=fG−fGNG′u∪uu∈U,fG−fGH2Gu∪u,where H2Gv is the 2-hop neighbors of v in the lower layer. Therefore, the best vertex is adjusted as u⟵argminv∈Gi△^Giv in Line 5 of algorithm 1 and other steps are the same.Example 4.
Reconsider the user-movie network in Figure1. Suppose α = 2, β = 2. According to the OS-I, we remove vertex v7 firstly and obtain the rational score of the remained 2,2-core. Then, we remove u6 and obtain the corresponding score of 0.6556. After removing u3, the obtained score is 0. So, we return the result by u2,u3,u4,v2,v3,v4 with a score of 0.6556.


## 4.2.2. Followers-Based Optimization (OS-II)

The second idea is motivated by the followers of each removal vertex. Generally, instead of removing one vertex and calculating the rational marginal gain, we remove a vertex with its all followers from the current candidate graph that have the smallest attribute marginal gain. Hence, the marginal score is modified as the following equation:(4)△˜Gu=fG−fGℱGu,and the other steps are the same as BGF.Example 5.
Reconsider the example in Figure1. Suppose α = 2, β = 2. According to the OS-II, vertex u7 is removed firstly and the obtained score is 0.455333. Then, we remove v5 and calculate the score with 0.65556. After deleting u2, the score is 0. Therefore, we return the result u2,u3,u4,v2,v3,v4 with a score of 0.65556.


## 4.2.3. Analysis

The main difference between BGF and optimized algorithm is the best vertex. In BGF, calculating the marginal score of a vertex isO1 time. In OS-II, the time complexity of identifying the followers of the vertex is Om, which may significantly increase the running time.


## 5. Experiments

### 5.1. Algorithms

To the best of our knowledge, there is no existing work for RCD-ABG problem. In the experiments, we implement and evaluate the following algorithms.(i)
BGF. The baseline greedy framework is presented in Algorithm 2, which iteratively peels the graph and returns the best result during the search(ii)
OS-I. OS-I leverages the baseline framework BGF and further integrates the proposed 2-hop neighbor-based optimization(iii)
OS-II. OS-II leverages the baseline framework BGF and further integrates the proposed follower-based optimization(iv)
ORI. To evaluate the advantage of proposed model, we also implement the traditional α,β-core search method [10], which iteratively removes the vertex that violates the degree constraints and returns the final subgraph


### 5.2. Datasets and Workloads

We employ 6 real-world bipartite graphs. Among these datasets, CiaoDVD and TripAdvisor can be obtained on KONECT (https://konect.uni-koblenz.de). Other datasets are publicly available on GroupLens (https://grouplens.org/datasets/). The statistics of datasets are shown in Table 2, where A is the number of attributes in bipartite graphs. HetRec (HR) [18] is a user-artists network, where the attribute of edges denotes the number of time that user listens to the music by the artist. CiaoDVD (CD) and MovieLens (ML) [18] are user-movie networks of which the attributes of relationships represent the ratings for movie. TripAdvisor is a user-hotel bipartite graphs and the attribute of its edges denotes the rating taken by users. The BookCrossing (BC) is a user-book network and the edges of it denote the book-rating taken by user. Due to the density of graphs, α=β vary from 5 to 25 in HetRec, CiaoDVD, and TripAdvisor, vary from 15 to 35 in BookCrossing and vary from 50 to 250 in MovieLens and Personality. λ is set as 0.7 because the density of community will strengthen with the continuous deletion of vertices; thus, we focus on consensus score. All the programs are implemented in standard C++. All the experiments are performed on a server with an Intel Xeon 2.4 GHz CPU and 128 GB main memory.Table 2
Statistics of datasets.
DatasetULEAHetRec (HR)2,10118,74692,8355CiaoDVD (CD)17,61516,12172,3455TripAdvisor (TA)145,3161,759175,6555MovieLens (ML)71,53565,134855,5985BookCrossing (BC)278,855270,981941,14810Personality (PY)1,822198,1181,028,7515


### 5.3. Efficiency Evaluation

To evaluate the efficiency, we report the response time of algorithms by varyingα and β in Figures 2(a)–2(f). As observed, the time cost of OS-I and OS-II is more than BGF. This is because OS-I needs to calculate 2-hop neighbors of vertex in the lower layer and OS-II needs to calculate followers of vertex. Although the time complexity of OS-I and OS-II is more complex than BGF, there is not much difference of response time between them. We can observe that when α and β increase, the response time decreases for all methods. This is because the community size decreases.Figure 2
Efficiency evaluation by varying parametersα and β. (a) HetRec. (b) CiaoDVD. (c) TripAdvisor. (d) MovieLens. (e) BookCrossing. (f) Personality.
(a)(b)(c)(d)(e)(f)


### 5.4. Effectiveness Evaluation

To evaluate the effectiveness, we compare BGF, OS-I, and OS-II with ORI and report the rational score of the returned community. ORI is based on the traditionalα,β-core model. It first computes the α,β-core of the graph and then directly returns the connected component with the largest rational score. The results are shown in Figures 3(a)–3(f). We can observe that original α,β-core has very small rational score. OS-I and OS-II significantly outperform BGF over all the datasets, namely, find community with higher score than BGF. The score returned by OS-I is at least 0.01 higher than the one returned by BGF in all datasets. Due to the feature of the consensus score, the improvement of OS-I is already significant for the overall performance. The rational score decreases when α and β increase because of tighter degree constraint.Figure 3
Effectiveness evaluation by varying parametersα and β. (a) HetRec. (b) CiaoDVD. (c) TripAdvisor. (d) MovieLens. (e) BookCrossing. (f) Personality.
(a)(b)(c)(d)(e)(f)


### 5.5. Case Study

To further evaluate the advantage of the proposed model, we conduct a case study on HetRec dataset. The results are shown in Figure4. As shown, the movie and user are marked with different colors. The different-color edges denote different scores. The community in the solid line that consists of enlarged vertices and bold edges is the returned result. As we can see, it can find a more rational community with a high preference and density structure.Figure 4
Case study.


## 5.1. Algorithms

To the best of our knowledge, there is no existing work for RCD-ABG problem. In the experiments, we implement and evaluate the following algorithms.(i)
BGF. The baseline greedy framework is presented in Algorithm 2, which iteratively peels the graph and returns the best result during the search(ii)
OS-I. OS-I leverages the baseline framework BGF and further integrates the proposed 2-hop neighbor-based optimization(iii)
OS-II. OS-II leverages the baseline framework BGF and further integrates the proposed follower-based optimization(iv)
ORI. To evaluate the advantage of proposed model, we also implement the traditional α,β-core search method [10], which iteratively removes the vertex that violates the degree constraints and returns the final subgraph


## 5.2. Datasets and Workloads

We employ 6 real-world bipartite graphs. Among these datasets, CiaoDVD and TripAdvisor can be obtained on KONECT (https://konect.uni-koblenz.de). Other datasets are publicly available on GroupLens (https://grouplens.org/datasets/). The statistics of datasets are shown in Table 2, where A is the number of attributes in bipartite graphs. HetRec (HR) [18] is a user-artists network, where the attribute of edges denotes the number of time that user listens to the music by the artist. CiaoDVD (CD) and MovieLens (ML) [18] are user-movie networks of which the attributes of relationships represent the ratings for movie. TripAdvisor is a user-hotel bipartite graphs and the attribute of its edges denotes the rating taken by users. The BookCrossing (BC) is a user-book network and the edges of it denote the book-rating taken by user. Due to the density of graphs, α=β vary from 5 to 25 in HetRec, CiaoDVD, and TripAdvisor, vary from 15 to 35 in BookCrossing and vary from 50 to 250 in MovieLens and Personality. λ is set as 0.7 because the density of community will strengthen with the continuous deletion of vertices; thus, we focus on consensus score. All the programs are implemented in standard C++. All the experiments are performed on a server with an Intel Xeon 2.4 GHz CPU and 128 GB main memory.Table 2
Statistics of datasets.
DatasetULEAHetRec (HR)2,10118,74692,8355CiaoDVD (CD)17,61516,12172,3455TripAdvisor (TA)145,3161,759175,6555MovieLens (ML)71,53565,134855,5985BookCrossing (BC)278,855270,981941,14810Personality (PY)1,822198,1181,028,7515


## 5.3. Efficiency Evaluation

To evaluate the efficiency, we report the response time of algorithms by varyingα and β in Figures 2(a)–2(f). As observed, the time cost of OS-I and OS-II is more than BGF. This is because OS-I needs to calculate 2-hop neighbors of vertex in the lower layer and OS-II needs to calculate followers of vertex. Although the time complexity of OS-I and OS-II is more complex than BGF, there is not much difference of response time between them. We can observe that when α and β increase, the response time decreases for all methods. This is because the community size decreases.Figure 2
Efficiency evaluation by varying parametersα and β. (a) HetRec. (b) CiaoDVD. (c) TripAdvisor. (d) MovieLens. (e) BookCrossing. (f) Personality.
(a)(b)(c)(d)(e)(f)


## 5.4. Effectiveness Evaluation

To evaluate the effectiveness, we compare BGF, OS-I, and OS-II with ORI and report the rational score of the returned community. ORI is based on the traditionalα,β-core model. It first computes the α,β-core of the graph and then directly returns the connected component with the largest rational score. The results are shown in Figures 3(a)–3(f). We can observe that original α,β-core has very small rational score. OS-I and OS-II significantly outperform BGF over all the datasets, namely, find community with higher score than BGF. The score returned by OS-I is at least 0.01 higher than the one returned by BGF in all datasets. Due to the feature of the consensus score, the improvement of OS-I is already significant for the overall performance. The rational score decreases when α and β increase because of tighter degree constraint.Figure 3
Effectiveness evaluation by varying parametersα and β. (a) HetRec. (b) CiaoDVD. (c) TripAdvisor. (d) MovieLens. (e) BookCrossing. (f) Personality.
(a)(b)(c)(d)(e)(f)


## 5.5. Case Study

To further evaluate the advantage of the proposed model, we conduct a case study on HetRec dataset. The results are shown in Figure4. As shown, the movie and user are marked with different colors. The different-color edges denote different scores. The community in the solid line that consists of enlarged vertices and bold edges is the returned result. As we can see, it can find a more rational community with a high preference and density structure.Figure 4
Case study.


## 6. Conclusion and Future Work

In this paper, we propose and investigate the rationalα,β-core detection problem in attribute bipartite graphs. We formally define the problem and prove its NP-hardness. To solve this problem, a basic greedy framework is first presented, which iteratively removes the best vertex with the smallest marginal gain and calculate the remaining α,β-core. Two optimized strategies, namely, 2-hop neighbor-based optimization and follower-based optimization, are proposed to improve the performance. Experiments are conducted on real bipartite graphs to demonstrate the advantages of proposed model and techniques. As shown in the experience, the proposed model significantly outperforms the traditional α,β-core model. In real-world applications, there are also attributes within the vertices of the graphs. In the further work, we will consider more complex scenario to design the model and the corresponding approaches.



---

*Source: 4430087-2022-04-28.xml*