Multi-attributed Community Search in Road-social Networks

For example, Fig. 1 displays a road-social network, where vertices represent users and road junctions, and edges represent social relations and road segments, respectively. For simplicity, the location of user $v_{i}$ in Fig. 1(a) is on the vertex $r_{i}$ of the road network in Fig. 1(b). Fig. 2(a) shows the values of part of vertices in three different dimensions.

We introduce a novel densely connected substructure, called $(k,t)$-core, by focusing on the following structural cohesiveness and communication cost.

The maximal $k$-core is the one satisfying that no super $k$-core containing it exists. We refer to the maximal $k$ in all $k$-cores containing vertex $v\!\in\!V_{s}$ as the core number of $v$. In order to avoid confusion, we denote a connected $k$-core as a $k$-$\widehat{core}$, since the maximal $k$-core is not necessarily connected.

By query distance $D_{Q}(H)$, the communication cost between query vertices $Q$ and the members in $H$ can be measured. In general, a good community is considered to own a low communication cost, i.e., small $D_{Q}(H)$. Consider the query vertices $Q\!=\!\{v_{2},v_{3},v_{6}\}$ in Fig. 1. The query distance of $v_{7}$ is $D_{Q}(v_{7})\!=\!dist(r_{7},r_{6})\!=\!7$. The query distance of the subgraph induced by $\{v_{2},v_{3},v_{6},v_{7}\}$ is equal to $dist(r_{3},r_{6})\!=\!9$. In the following, we propose a new notion of $(k,t)$-core, by adapting the concepts of $k$-core and query distance, to capture dense structural cohesiveness and low communication cost.

For a $(k,t)$-core, its structural cohesiveness increases with $k$, while proximity to query vertices decreases with $t$. For instance, in Fig. 1, the subgraph induced by $\{v_{2},v_{3},v_{6},v_{7}\}$ for $Q\!=\!\{v_{2},v_{3},v_{6}\}$ is a $(k,t)$-core with $k\!=\!3$ and $t\!=\!9$.

Note that generalizing the existing community models, most of which are only for $1$-dimensional attribute such as influence [4], Euclidean distance [6] or keyword similarity [5, 7, 16, 17], to a comparable one with multi-dimensional attributes is nontrivial. Unlike the above, comparing two communities becomes quite tough if either can have $d$ ($d\!>\!1$) values due to $d$ different dimensions. On the other hand, existing multi-dimensional model [8] cannot compare the pros and cons of any skyline communities and make trade-offs based on user preferences. To overcome the above issues, we introduce the r-dominance relationship between two communities, that will be developed for defining our multi-attributed community model.

As each vertex $v\!\in\!V_{s}$ associated with a vector $X(v)$, the attributes define a $d$-dimensional data domain. We assume that for each attribute a higher value is preferable, and a spatial index (e.g., R-tree [18]) is used to organize the vector set $X$.

Referring to the traditional top-$j$ queries, the score of a vertex $v$ w.r.t $X(v)$ can also be derived by inputting a weight vector $w\!=\!(w_{1},w_{2},\ldots,w_{d})$ as

$$S(v)=\sum\nolimits_{i=1}^{d}w_{i}\cdot x_{i}^{v}.$$

(1)

Thus, the top-$j$ results consist of the $j$ vertices with the highest scores. We assume w.l.o.g. that $w_{i}\!\in\!(0,1)$ for $\forall i\!\in\![1,d]$ and $\sum_{i=1}^{d}w_{i}\!=\!1$. Such conditions cannot restrain user preferences, because score ranking depends only on the direction of $w$ instead of its magnitude [19]; but they allow $w$ to drop one weight (i.e., $w_{d}\!=\!1-\sum_{i=1}^{d-1}w_{i}$), thereby mapping the domain of $w$ to a ($d\!-\!1$)-dimensional space, named the preference domain. This dimensionality reduction is critical [20], since the dimensionality directly determines the processing time of the costliest operations in our techniques (see Section V-B). In the following, $w$ refers to the ($d\!-\!1$)-dimensional form of the weight vector. For example, given weights 0.2 and 0.3 for $x_{1}$ and $x_{2}$ respectively in Fig. 2(a), we have $w_{3}\!=\!0.5$, and $S(v_{7})\!=\!4.47$.

Intuitively, in the traditional sense of dominance [21, 22], for any weight vector $w$ the dominator is always superior to the dominee, while r-dominance is specific to weight vectors in $R$. Although a community may not dominate another based on the skyline community model [8], it might always have a higher score as $w$ is bounded in $R$. For ease of representation, we assume that $R$ is a hyper-rectangle parallel to axes, but our techniques is directly applicable to general convex polytopes.

For example, Fig. 2(b) illustrates a preference domain (i.e., the domain of weight vector) with $d\!=\!3$, where axis $w_{1}$ (resp. $w_{2}$) corresponds to the weight for $x_{1}$ (resp. $x_{2}$) on a scale of 0 to 1, and the region $R$ is a convex polygon (i.e., an axis-parallel rectangle $[0.1,0.5]\!\times\![0.2,0.4]$) representing the expanded or approximated user preferences.

Combining the notion of $(k,t)$-core and community score, we define the multi-attributed community (MAC) as follows.

In terms of structural cohesiveness and communication cost, condition (1) requires not only that the community with query vertices $Q$ contained is densely connected, but also that each vertex is spatially close to $Q$. In terms of maximality and multi-attributed community score, condition (2) ensures that the community is maximal and having the greatest score. The following example illustrates Definition 5.

For most practical applications, we typically tend to focus on the query-user-involved communities, which score higher than (i.e., r-dominate) all other communities in the preference domain $R$. In this paper, we aim to efficiently discover such communities in road-social networks. Below, two multi-attributed community search problems are formulated.

For Problem 1, an MAC may be contained in another MAC in the top-$j$ results.

To eliminate the containment relations in the top-$j$ results, we study another problem of finding the non-contained MAC.

The following example illustrates Definition 6.

Consider two vertices $v$ and $v^{\prime}$ where none dominates the other in terms of traditional dominance, that may not draw a reliable conclusion about which vertex ranks higher. Nevertheless, given a preference domain, the inequation $S(v)\!\geq\!S(v^{\prime})$ (resp. equation $S(v)\!=\!S(v^{\prime})$) corresponds to a half-space (resp. hyperplane), of which there are three different cases regarding the positioning against $R$ [13]. Specifically, in Fig. 3(a), $v$ r-dominates $v^{\prime}$ since half-space $HS:S(v)\!\geq\!S(v^{\prime})$ completely covers $R$, which means $v$ scores higher for $\forall w\in R$; the case in Fig. 3(c) is symmetric. In Fig. 3(b), $v$ scores higher in one part of $R$ but lower in another, which is called r-incomparable as none r-dominates the other.

Clearly, the cases in Fig. 3(a) and 3(c) allow r-dominance conclusions to be safely drawn. In this way, we can determine r-dominance by detecting whether all polygon vertices defining $R$ fall into the half-space $HS:S(v)\!\geq\!S(v^{\prime})$. If so (resp. not), $v$ r-dominates (resp. is r-dominated by) $v^{\prime}$. Otherwise, $v$ and $v^{\prime}$ are r-incomparable. The inclusion detecting of each polygon vertex costs $O(d)$, so the r-dominance test requires $O(pd)$ in total, where $p$ is the number of polygon vertices defining $R$.

The computation of r-dominance relationships is somewhat similar to that of the $k$-skyband (i.e., BBS [26]), but differs as follows. (1) Rather than traditional dominance, we employ r-dominance and apply its test described in Section IV-A both for vertex-to-vertex and vertex-to-MBB (i.e., minimum bounding box) dominance testing. (2) Due to the fact that $w$ is bounded in $R$, we adopt a unique sorting key for R-tree nodes (represented by MBB’s upper-right corner) and vertices in the heap to accelerate search convergence by leading it to r-dominate as many members as possible first. (3) We preserve the r-dominance relationships between vertices in $H_{k}^{t}$ instead of only the top-$j$ layers. It is noting that a max-heap is utilized in our adapted BBS and its sorting key is the score of R-tree node/vertex w.r.t. a pivot vector of $R$, whose value of each dimension is the mean of the polygon vertices of $R$ in that dimension [13]. The correctness of our adaptation is guaranteed as follows. (1) The pivot vector must lie in $R$ due to $R$’s convexity [27]. (2) Vertices popped after $v$ cannot r-dominate $v$ due to pivot-based sorting (in decreasing order).

In addition, we adopt a directed acyclic graph (DAG) [28, 22] to maintain all pair-wise r-dominance relationships between vertices in $H_{k}^{t}$, named r-dominance graph (denoted by $G_{d}$). Fig. 4(b) illustrates $G_{d}$ of $H_{3}^{9}$. An arc from vertex $v$ to $v^{\prime}$ signifies that $v$ r-dominates $v^{\prime}$. It is noting that an arc from $v_{6}$ or $v_{2}$ to $v_{7}$ is not needed as the transitivity of r-dominance relationship already implies this. The number of vertices that r-dominate $v$ is called $v$’s r-dominance count.

The idea of the DFS-based algorithm is described in detail in Algorithm 1. First, for given $k$ and $t$, we compute the maximal $(k,t)$-core, i.e., $H_{k}^{t}$, and build the r-dominance graph $G_{d}$. Then, the following procedure is iteratively invoked until the resulting graph in each partition of $R$ does not have a $k$-$\widehat{core}$ containing $Q$. The procedure consists of two steps. Let $H$ and $G_{d}^{\prime}$ be the resulting subgraph and corresponding r-dominance graph in partition $\rho$ of $R$ (Line 6). The first step is to insert sub-partitions into $\rho$ according to $G_{d}^{\prime}$ (Lines 7-9), then find the smallest-score vertex in each sub-partition (Lines 10-11). In Line 9, note that $\rho$ is the root node of a binary tree after being passed in as a parameter, and $S$ is a set of leaf nodes of the binary tree, representing sub-partitions of $\rho$. This step is essential and will be elaborated in Section V-B. The second step is to delete all the vertices that are definitely excluded in subsequent MACs, which enables $H$ and $G_{d}^{\prime}$ to be updated accordingly (Lines 15-20).

In particular, Algorithm 1 recursively deletes all the vertices violating the structural cohesiveness constraint by a DFS procedure (Lines 16-19) as long as the smallest-score vertex $u$ is found in the sub-partition. Because the degrees of the adjacent vertices of $u$ all reduce by 1 when we delete $u$. This may cause some neighbors of $u$ to violate the structural cohesiveness constraint and thus cannot be contained in subsequent MACs. Likewise, we also need to verify whether the neighbors of other hops (e.g., 2-hop, 3-hop, etc.) meet the structural cohesiveness constraint. Obviously, the DFS procedure can be used to identify and delete all these vertices.

According to Lemma 6, we have a corollary as follows.

Note that we always consider the early termination conditions of Corollary 1 in conjunction with the DFS procedure. Once either is met, it means that vertex $u$ cannot be deleted, even if $u$ is currently the one with the smallest score but $H$ is already the non-contained MAC w.r.t. partition $\rho^{\prime}$ (Line 12). As a result, if Corollary 1 (i.e., Lemma 6) holds, the top-$j$ MACs can be obtained by the union of top vertices in heap $I^{\prime}$ (totally backtracking $j\!-\!1$ times) and the last subgraph $H$ (Line 13). Based on Lemma 4 and 5, we can easily verify that $H$ for each partition $\rho$ recursively obtained in Line 6 is an MAC. Thus, Theorem 1 shows the correctness of Algorithm 1.

Proof Sketch: For any partition $\rho$, as long as its current subgraph $H$ does not hold Corollary 1, $\rho$ will be divided into $|S|$ sub-partitions by $|HP|$ hyperplanes (Line 10 in Algorithm 1), e.g., $\rho_{i}$ for $1\leq i\leq|S|$. Here, $\rho$ is discarded when the recursion proceeds to the promising sub-partitions of the local arrangement, i.e., $\rho_{i}$. Assume that $u$ is the smallest-score vertex in $H$ w.r.t. $\rho_{i}$, the resulting subgraph, denoted by $H_{i}$, obtained by invoking DFS procedure (Line 12 in Algorithm 1) can be claimed as the maximal $k$-$\widehat{core}$ of the subgraph $H\backslash u$ by contradiction, because DFS procedure recursively deletes all the vertices in $H$ whose degrees are smaller than $k$. Therefore, we have $V_{H_{i}}\subset V_{H}$ and $S(H)\leq S(H_{i})$ w.r.t. $\rho_{i}$ for $1\leq i\leq|S|$. In this way, the non-contained MAC corresponding to each final sub-partition can be found, as well as all the MACs. Thus, we conclude that Algorithm 1 correctly finds the top-$j$ MACs. $\square$

We analyze the complexity of Algorithm 1 in Theorem 2.

In Algorithm 1, to find the smallest-score vertex for any weight vector in partition $\rho$, we consider the vertices of $G_{d}^{\prime}$ in a bottom-up manner. In other words, leaf vertices of the r-dominance graph will be preferred (Line 7). The reason is that if a vertex is deleted either because it does not satisfy the structural cohesiveness constraint (already considered in the DFS procedure), or because it is the smallest-score vertex, but before this, all vertices it r-dominates should be deleted first.

The verification of a leaf vertex $u$ in $G_{d}^{\prime}$ entails partitioning $\rho$ by half-spaces $HS_{i}:S(u^{\prime})\!\geq\!S(u)$, each corresponding to one of the remaining leaf vertex $u^{\prime}$. Formally, an arrangement bounded by $R$ is defined by the supporting hyperplanes of these half-spaces, where each cell (i.e., sub-partition) is located in a set of half-spaces. The leaf vertices corresponding to these half-spaces are precisely those with scores higher than $u$ if $w$ falls in that cell, which means $u$ is the smallest-score vertex.

Consider $G_{d}$ in Fig. 4(b). Initially, the leaf vertices are $v_{7}$, $v_{5}$ and $v_{1}$ ($G_{d}^{\prime}\!=\!G_{d},I^{\prime}\!=\!\emptyset$, Line 6 in Algorithm 1). Their respective half-spaces $HS_{1}:S(v_{7})\!\geq\!S(v_{5})$, $HS_{2}:S(v_{7})\!\geq\!S(v_{1})$ and $HS_{3}:S(v_{1})\!\geq\!S(v_{5})$ are inserted into the arrangement, as shown in Fig. 5(a). The vertex in brackets for each partition indicates the smallest-score vertex for any weight vector $w$ in that partition. For partitions $\rho_{3}$ and $\rho_{4}$ on the right, vertex $v_{1}$ will also be deleted by the DFS procedure due to the deletion of $v_{7}$, after which $v_{1}$ and $v_{7}$ are both pushed into the heap $I^{\prime}$ w.r.t. the partitions (representing the vertices ignored). Thus, the resulting subgraph $H$ induced by $\{v_{2},\ldots,v_{6}\}$ is the corresponding non-contained MAC since discarding any vertex will no longer satisfy the structural cohesiveness constraint. By backtracking the top vertices in $I^{\prime}$ once (i.e., $v_{1}$ and $v_{7}$), we can easily obtain the second-ranked MAC induced by $\{v_{1},\ldots,v_{7}\}$ in $\rho_{3}$ and $\rho_{4}$ (refer to $R_{3}$ in Fig. 2(b)).

When Corollary 1 does not hold, sub-partition $\rho^{\prime}$ will be pushed into queue $U$ to compute the non-contained MAC in depth. At this time, vertices ignored will be discarded to update resulting subgraph $H$ and corresponding $G_{d}^{\prime}$, so that new leaf vertex can be designated in the next round of verification and the half-spaces against other leaf vertices are inserted into the local arrangement. Consider $\rho_{1}$ in Fig. 5(a), we refer to $v_{4}$ as the new leaf vertex after $v_{1}$ is deleted, i.e., $H$ and $G_{d}^{\prime}$ are induced by $\{v_{2},\ldots,v_{7}\}$ and $I^{\prime}=\{v_{1}\}$. Then, new half-spaces $HS_{4}:v_{7}\!\geq\!v_{4}$ and $HS_{5}:v_{5}\!\geq\!v_{4}$ are inserted into a newly initialized local arrangement against partition $\rho_{1}$, where three sub-partitions $\rho_{5}$, $\rho_{6}$ and $\rho_{7}$ are produced, as shown in Fig. 5(b). As $v_{4}$ and $v_{5}$ are pushed into $I^{\prime}$ together, the non-contained MAC induced by $\{v_{2},v_{3},v_{6},v_{7}\}$ is returned for each sub-partition. Likewise, same operation applies to partition $\rho_{2}$. Eventually, the solution in Example 3 is obtained. Note that we can directly locate $HS_{4}$ and $HS_{5}$ for $\rho_{2}$ since no new half-space needs to be computed due to the same leaf vertices (in $G_{d}^{\prime}$) as $\rho_{1}$. This drastically reduces repetitive computation in half-spaces, each of which is computed only once if necessary.

Specifically, for each local arrangement considered, an index is built by a recursive process Partition (Algorithm 2). Then, the index is discarded when all relevant half-spaces are inserted, leaving only the hopeful sub-partitions of the local arrangement (if any). Note that, for any index of $\rho$ (Line 9 in Algorithm 1), the total cost of inserting the $i$-th hyperplane $hp$ is $O(i^{d-1})$ [20]. In addition, optimization of arrangement indexing and maintenance is the same as described in [13].

To be a candidate for non-contained MACs, the current community must be at least a $k$-$\widehat{core}$ containing $Q$. It would be nice if the structural cohesiveness metric (i.e., $k$-core) is “monotonic”, which means that the larger the community, the smaller its minimum degree. So once the minimum degree drops below the given coreness threshold $k$, we can stop the search. Unfortunately, such a metric is not monotonic. Thus, the greatest challenge is to overcome non-monotonicity first, which motivates us to conduct community search only by exploring local neighborhood of $Q$.

Now for the minimum degree of a subgraph $H$, denoted by $\delta(H)$, we make an in-depth analysis of its monotonicity. Consider the exploration starting from the query vertices, i.e., $H_{0}$ induced by $Q$. We add a vertex from $H_{k}^{t}$ at each step until a $k$-$\widehat{core}$ $H$ is obtained, assuming that $v_{1},v_{2},\ldots,v_{e}$ is a vertex sequence it adds. So let $H_{i}$ be induced by $Q\cup\{v_{1},\ldots,v_{i}\}$. In general, $\delta(H)$ is a non-monotonic function of $H$. More formally, $\delta(H_{i+1})$ is unnecessarily greater than $\delta(H_{i})$. However, the order of vertices added to $V_{H}$ determines the monotonicity of $\delta(H)$. Interestingly, for any $Q$ with $\delta(H_{0})=0$, we can always find a sequence of added vertices such that $\delta(H_{i})$ is a non-decreasing function of $i$.

Proof Sketch: It is consistent with proving that vertices can be removed one by one from $V_{H}$ until $Q$, just ensuring that each removal of $v$ does not increase the minimal degree of the remaining vertices. Otherwise, it occurs only when $v$ is currently one of the vertices with the minimal degree. The reason is that removing a vertex with non-minimal degree will only preserve or decrease the minimal degree. $\square$

Lemma 7 implies that there always exists an exploration order that leads monotonically to a community of $k$-$\widehat{core}$ containing $Q$. This can be generated by a sequence of vertices added to $V_{H}$ starting from $Q$ so that $\delta(H_{i})\leq\delta(H_{i+1})$ for each $i$. Note that the existence of such an order is a necessary but insufficient condition for finding a valid community. To illustrate the insufficiency, consider $Q=\{v_{9}\}$ and $k=2$ in Fig. 1(a). Any vertex sequence starting with $v_{9},v_{14}$ cannot yield a valid solution, yet $\delta(H_{1})$ is greater than $\delta(H_{0})$.

In Expand procedure (Algorithm 4), we explore from the vicinity of $Q$ by BFS and generate candidate set $C$. To converge the current community towards a candidate for non-contained MAC, we develop two intelligent candidate selection strategies according to Lemma 3, 6 and 7. The idea of improving candidate generation is to use priority queues such that the most promising vertex can be selected to rapidly generate a candidate. From the perspective of structural cohesiveness, the priority of a vertex $v$ can be defined as $f_{1}(v)=\delta(H^{\prime})-\delta(H)$ or $f_{2}(v)=dg_{H^{\prime}}(v)$, where $V_{H}^{\prime}=V_{H}\cup\{v\}$. $f_{1}(v)$ emphasizes the improvement of minimum degree for the next step, with $f_{1}(v)=1$ or $0$ for any $v$; $f_{2}(v)$ produces the fastest increase in average degree of $H$ so that the minimum degree will increase with $H$’s density growth. From the perspective of community score, the priority of $v$ can be defined as $f_{3}(v)=\zeta-l(v)$, where $\zeta$ is a constant (maximum priority in $G_{d}$) and $l(v)$ denotes the layer of $v$ in $G_{d}$. $f_{3}(v)$ drives community score higher by adding a vertex that r-dominates as many vertices as possible. To sum up, the priority $f(v)$ is defined as

$$f(v)=\lambda\!\cdot\!f_{2}(v)+f_{3}(v),$$

(3)

where $\lambda$ is a trade-off against $\zeta$, or

$$f(v)=\zeta\cdot f_{1}(v)+f_{3}(v).$$

(4)

The determinant of global search is that computing the local arrangement of all half-spaces $HS_{i}$ among leaf vertices is a relatively expensive process (in $O({i^{*}}^{d})$ time [29], where $i^{*}$ is the number of half-spaces). Instead, in Verify procedure (Algorithm 5), an empty arrangement in $R$ is initialized, into which half-spaces w.r.t. a carefully selected and therefore very small subset of vertices (i.e., competitors below) are inserted, expecting to securely confirm or disqualify candidate $H$ without considering all other vertices. But before this, we first give a corollary to filter out unpromising candidates from $C$. Note that $G_{e}$ represents the r-dominance graph corresponding to $H$, which is a subgraph of $G_{d}$ induced by $V_{H}$, denoted by $G_{d}[V_{H}]$; and $G_{c}$ represents the rest of $G_{d}$, denoted by $G_{d}[V_{G_{d}}\!\backslash\!V_{H}]$.

Proof Sketch: Vertices in $V_{G_{d}}\!\backslash\!V_{H}$ must be deleted if $H$ holds. $\square$

In other words, either there exists a non-cross-layer arc in $G_{c}$ between a non-leaf vertex $v$ and a leaf vertex, or $v$ can be recursively deleted by the DFS procedure. We refer to the $H$ that holds Corollary 2 as a promising community.

Now we discuss the verification process by half-space insertion, in which it may further benefit from the r-dominance relationships stored in $G_{d}$ as follows.

Based on Lemma 9, competitors chosen are the vertices in the bottom layer (leaf vertices) of $G_{e}$ and in the top layer (with r-dominance count 0) of $G_{c}$, denoted by $l_{b}(G_{e})$ and $l_{t}(G_{c})$ respectively. The fundamental is that intuitively such competitors are the strongest, which are most likely to assist in disqualifying invalid candidates w.r.t. $R$ in turn.

To illustrate Algorithm 5, let us reconsider Example 2. Assume that by Algorithm 4 we have three promising communities $H_{1}$, $H_{3}$ and $H_{4}$, where $V_{H_{1}}\!=\!\{v_{2},v_{3},v_{6},v_{7}\}$, $V_{H_{3}}\!=\!\{v_{2},\ldots,v_{6}\}$ and $V_{H_{4}}\!=\!\{v_{1},v_{2},v_{3},v_{6},v_{7}\}$. For $H_{1}$, $l_{b}(G_{e})\!=\!\{v_{7}\}$ and $l_{t}(G_{c})\!=\!\{v_{4},v_{5}\}$. As $v_{4}$ and $v_{5}$ are bound to each other in $H_{3}^{9}$ (condition (3) met), we only insert $HS_{1}$ and $HS_{4}$ into $R$ in Fig. 5(b), and choose the partitions covered by either of them. As a result, $H_{1}$ is a valid non-contained MAC for any weight vector of $R_{1}$ in Fig. 2(b). Similarly, $H_{3}$ is also valid w.r.t. $R_{2}\cup R_{3}$ (condition (2) met) but $H_{4}$ is invalid (condition (1) met) as its partition is outside $R$.

Finally, we can simply generalize local search for Problem 1. As the non-contained MAC $H$ with corresponding partition $\rho$ is known, we insert sub-partitions into $\rho$ according to $G_{c}$ (in a up-bottom manner) and add the highest-score vertex to $H$. As long as the current $H$ contains an MAC, it will be output. The process terminates until all top-$j$ MACs in $\rho$ are acquired. Consider $H_{1}$ and its $G_{c}$, half-spaces among vertices in $l_{t}(G_{c})$ (i.e., $HS_{5}$) are inserted first into $R_{1}$. Then $v_{5}$ is added to $V_{H_{1}}$ for $\rho_{5}$ and $\rho_{8}$ shown in Fig. 5(b). As $v_{4}$ r-dominates $v_{1}$, we have the second MAC induced by $\{v_{2},\ldots,v_{7}\}$ in $\rho_{5}$ and $\rho_{8}$. The same applies to $\rho_{6}$ and $\rho_{7}$.