Figures (14)  Tables (11)

    • Figure 1. 

      An example of the semantic-rich HIN DBpedia.

    • Figure 2. 

      Diverse semantically similar communities.

    • Figure 3. 

      The schema of the HIN illustrated in Fig. 1 with five example meta-paths between nodes with a type $\mathrm{Person}$.

    • Figure 4. 

      Parallel $ {\cal{P}}^* $-neighbor expansion.

    • Figure 5. 

      Efficiency comparison.

    • Figure 6. 

      Effect of $ \hat{l} $ on efficiency.

    • Figure 7. 

      Effect of $ \hat{l} $ on effectiveness metrics (NMP and SC).

    • Figure 8. 

      Effect of $ k $ on efficiency.

    • Figure 9. 

      Effect of $ k $ on effectiveness metrics (NMP and SC).

    • Figure 10. 

      Effect of $ r $ on efficiency.

    • Figure 11. 

      Effect of $ r $ on effectiveness metrics (NMP and SC).

    • Figure 12. 

      Effect of $ b $ on efficiency.

    • Figure 13. 

      Effect of # threads on efficiency.

    • Figure 14. 

      Case studies on DBpedia.

    • Input: HIN $ G $, SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, $ q $, $ k \geq $ 0, $ r \geq 1 $
      Output: top-$ r $ SICs with highest semantic cohesiveness
      1 $ \mathrm{HSet} \leftarrow \emptyset $; $ \mathrm{SemSet}\leftarrow \emptyset $; $ H^{\prime} \leftarrow \emptyset $;
      2 $ \mathrm{count} \leftarrow $ 0; // $ \mathrm{ number of SICs}$
      3 $ \mathrm{R} \leftarrow \{ S_i \in {\cal{R}} \} $, in descending order of $ W_{S_i\rightarrow S} $;
      4 while: ${\it{\mathrm{count}}} \lt r $ do
      // $\mathrm{Step (1): Semantic expansion} $
      5 if $ |{\it{\mathrm{SemSet}}}| = |{\it{\mathrm{R}}}| $ then
      6 break;
      7 $ \mathrm{SemSet} \leftarrow \mathrm{SemSet}\cup\mathrm{R} $.poll();
      // $\mathrm{Step (2): } G_{\mathrm{SMP}} \mathrm{ construction } $
      8 $ G_{\text{SMP}} \leftarrow \mathrm{getSMPGraph} (G, \text{SMP}, q, \mathrm{SemSet}) $;
      // $\mathrm{Step (3): SIC extraction} $
      9 $ H \leftarrow $ find a connected ($ k $,SMP)-core of $ q $ from $ G_{\text{SMP}} $;
      10 if $ H $ does not exist then
      11 continue;
      // $\mathrm{Step (4): Quality evaluation} $
      12 if $ |V(H)| \gt |V(H^{\prime})| $ then
      13 $ \mathrm{HSet} \leftarrow \mathrm{HSet} \cup H $;
      14 $ H^{\prime} \leftarrow H $;
      15 $ \mathrm{count} \leftarrow \mathrm{count}+1 $;
      16 return ${\it{\mathrm{HSet}}}$;

      Table 1. 

      $\mathrm{Basic}$.

    • Input: HIN $ G $, SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, $ q $, $\mathrm{SemSet}$
      Output: $ q $-centric SMP-graph $ G_{\text{SMP}} $
      1 $\mathrm{Expand} \leftarrow q $; $ \mathrm{Visited} \leftarrow \emptyset $; $ G_{\text{SMP}} \leftarrow \emptyset $;
      2 while: $ \mathrm{Expand} \neq \emptyset $ do
      // $ \mathrm{Step (1): Neighbor retrieval} $
      3 $ u \leftarrow \mathrm{Expand} $.poll();
      4 $ \langle N^*(u), E^*(u) \rangle \leftarrow \mathrm{FPN}$($ G, u $, SMP, $\mathrm{SemSet}$);
      // $ \mathrm{Step (2): Graph update} $
      5 $ G_{\text{SMP}} \leftarrow G_{\text{SMP}} \cup \langle N^*(u), E^*(u) \rangle $;
      6 $ \mathrm{Visited} \leftarrow \mathrm{Visited} \cup \{u\} $;
      7 $ \mathrm{Expand} \leftarrow \mathrm{Expand} \cup (N^*(u) \setminus \mathrm{Visited}) $;
      8 return $ G_{\text{SMP}} $;

      Table 2. 

      $\mathrm{getSMPGraph}$($ G $, SMP, $ q $, $\mathrm{SemSet}$).

    • Input: HIN $ G $, node $ u $, SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, $ q $, $\mathrm{SemSet}$
      Output: $ {\cal{P}}^* $-neighbors and edges of node $ u $ $ \langle N^*(u), E^*(u) \rangle $
      1 $ N^*(u) \leftarrow \emptyset $; $ E^*(u) \leftarrow \emptyset $;
      2 $ \mathrm{NbrExpand} \leftarrow u $;
      3 $ \mathrm{Path} \leftarrow p_{uu} $;
      4 while: $ \mathrm{NbrExpand} \neq \emptyset $ do
      // $\mathrm{Step (1): Neighbor exploration} $
      5 $ w \leftarrow \mathrm{NbrExpand} $.poll();
      6 $ p_{uw} \leftarrow \mathrm{Path} $.poll();
      7 $ \mathrm{Neighbor}(w) \leftarrow $ w's neighbors in $ G $;
      8 while: $ \mathrm{Neighbor}(w) \neq \emptyset $ do
      // $\mathrm{Step (2): Path extension} $
      9 $ v \leftarrow \mathrm{Neighbor}(w) $.poll();
      10 if $ \mathrm{SemSet} $.contains($ \psi(e_{wv}) $) then
      11 $ p_{uv} \leftarrow p_{uw} \cup e_{wv} $;
      12 if $ u=v $ then
      13 continue;
      // Step (3): Neighbor update
      14 if $ p_{uv} $.length() $ \leq \hat{l} $ and $ \phi(v) = A_t $ and $ \phi(x) = A_a $ ($ x $ is a node in $ p_{uv} $) then
      15 $ N^*(u) \leftarrow N^*(u) \cup v $;
      16 $ E^*(u) \leftarrow E^*(u) \cup p_{uv} $;
      17 else if $ p_{uv} $.length() $ \lt \hat{l} $ then
      18 $ \mathrm{NbrExpand} \leftarrow \mathrm{NbrExpand} \cup v $;
      19 $ \mathrm{Path} \leftarrow \mathrm{Path} \cup p_{uv} $;
      20 return $ \langle N^*(u), E^*(u) \rangle $;

      Table 3. 

      $\mathrm{FPN}$($ G, u $, SMP, $\mathrm{SemSet}$).

    • Input: HIN $ G $, SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, $ q $, $ k \geq $ 0, $ r\geq 1 $, $ b \gt 1 $
      Output: top-$ r $ SICs with highest semantic cohesiveness
      1 $ \mathrm{HSet} \leftarrow \emptyset $; $ \mathrm{SemSet} \leftarrow \emptyset $; $ H^{\prime} \leftarrow \emptyset $;
      2 $ \mathrm{R} \leftarrow \{ S_i| S_i \in {\cal{R}} \} $, sorted in descending order;
      3 $ U \leftarrow $ 1;
      4 while: $ U \lt |\mathrm{R}| $ do
      // $ \mathrm{Step (1): Batch semantic expansion} $
      5 if $ U+b \lt |\mathrm{R}| $ then
      6 $ D = U+b $;
      7 else
      8 $ D = |\mathrm{R}| $;
      9 for $ i\leftarrow U $ to $ D $ do
      10 $ \mathrm{SemSet} \leftarrow \mathrm{SemSet} \cup \mathrm{R} $.get($ i $);
      // $ \mathrm{Step (2): Construct } G_\mathrm{SMP}$
      11 $ G_{\text{SMP}} \leftarrow \mathrm{getSMPGraph}(G, \text{SMP}, q, \mathrm{SemSet}) $;
      // $ \mathrm{Step (3): SIC extraction} $
      12 $ H \leftarrow $ find a connected ($ k $,SMP)-core of $ q $ from $ G_{\text{SMP}} $;
      // $ \mathrm{Step (4): Binary semantic search} $
      13 if $ H $ does not exist then
      14 $ U\leftarrow D+1 $;
      15 continue;
      16 else
      17 if $ |V(H)| \gt |V(H^{\prime})| $ then
      18 $ \mathrm{HSet} \leftarrow \mathrm{HSet} \cup \mathrm{BSS} $($ H' $, $ G_{\text{SMP}} $, $ U $, $ D $, $\mathrm{R}$, $ r $, $ |\mathrm{HSet}| $, $ q $);
      19 if $ |\mathrm{HSet}| $ = $ r $ then
      20 break;
      21 $ H^{\prime} \leftarrow H $;
      22 $ U\leftarrow D+1 $;
      23 else
      24 $ U\leftarrow D+1 $;
      25 continue;
      26 return ${\it{\mathrm{HSet}}}$;

      Table 4. 

      $\mathrm{Opt-BSS}$.

    • Input: $ H' $, $ G_{\text{SMP}} $, $ U \gt 0 $, $ D \gt 0 $, $\mathrm{R}$, $ r \geq 1 $, $ \mathrm{count} \geq $ 0, $ q $
      Output: top-$ r $ SICs with highest semantic cohesiveness
      1 $\mathrm{left} \leftarrow U $; $ \mathrm{right} \leftarrow D $;
      2 $\mathrm{HSet} \leftarrow \emptyset $; $ \mathrm{SemSet}\leftarrow \emptyset $;
      3 while $ \mathrm{left} \leq \mathrm{right} $ do
      // $\mathrm{Termination check}$
      4 if $\mathrm{count}$ = $ r $ then
      5 break;
      6 if $\mathrm{count}$ = 0 then
      7 $ H^{\prime} \leftarrow \emptyset $;
      // $\mathrm{Step (1): Midpoint selection}$
      8 $\mathrm{mid}$ = $\mathrm{left}$ + $ \lfloor (\mathrm{right} - \mathrm{left}) / 2 \rfloor $;
      9 $\mathrm{SemSet}\_\mathrm{BSS} \leftarrow \emptyset $;
      10 for $ i \leftarrow 1 $ to $\mathrm{mid}$ do
      11 $ \mathrm{SemSet}\_\mathrm{BSS} \leftarrow \mathrm{SemSet}\_\mathrm{BSS} \cup \mathrm{R} $.get($ i $);
      // $\mathrm{Step (2) and (3)}$
      12 $ G'_{\text{SMP}} \leftarrow $ find a smaller $ G'_{\text{SMP}} $ using $\mathrm{SemSet}\_\mathrm{BSS}$;
      13 $ H \leftarrow $ find a connected ($ k $,SMP)-core of $ q $ from $ G'_{\text{SMP}} $;
      // $\mathrm{Step (4): SIC refinement}$
      14 if $ H $ exists and $ |V(H)| \gt |V(H^{\prime})| $ then
      15 if $\mathrm{mid}$ = $\mathrm{left}$ then
      16 $ H' \leftarrow H $;
      17 $\mathrm{count}$ = $\mathrm{count}$ + 1;
      18 $\mathrm{HSet} \leftarrow \mathrm{HSet} \cup H $;
      19 $\mathrm{left} \leftarrow \mathrm{mid} +1 $;
      20 $\mathrm{right} \leftarrow D $;
      21 continue;
      22 else
      23 $\mathrm{right}$ = $\mathrm{mid}-1 $;
      24 else
      25 $\mathrm{left}$ = $\mathrm{mid}+1 $;
      26 if $\mathrm{left} \gt \mathrm{right}$ then
      27 $\mathrm{SemSet}\_\mathrm{BSS} \leftarrow \mathrm{SemSet}\_\mathrm{BSS} \cup \mathrm{R} $.get($ \mathrm{left}$);
      28 repeat lines 12-13;
      29 if $ H $ exists then
      30 repeat lines 16−21;
      31 return ${\it{\mathrm{HSet}}}$;

      Table 5. 

      $\mathrm{BSS}$($ H' $, $ G_{\text{SMP}} $, $ U $, $ D $, $\mathrm{R}$, $ r $, $ \mathrm{count}$, $ q $).

    • Input: HIN $ G $, SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, query node $ q $, integer $ k \geq $ 0, integer $ r \gt 0 $, integer $ b \gt 1 $
      Output: SICs with top-$ r $ semantic cohesiveness
      1 $\mathrm{HSet} \leftarrow \emptyset $; $ \mathrm{SemSet} \leftarrow \emptyset $; $ H^{\prime} \leftarrow \emptyset $;
      2 $\mathrm{R} \leftarrow \{ S_i| S_i \in {\cal{R}} \} $, sorted in descending order;
      3 $ U \leftarrow $ 1; $\mathrm{count} \leftarrow $ 0; //
      4 while: $ U \lt |\mathrm{R}| $ do
      // $\mathrm{Step (1)-(3)}$
      5 lines 5-12 in $\mathrm{Opt-BSS}$ (Algorithm 4)
      // $\mathrm{Step (4): Binary semantic search with recording}$
      6 if $ H $ does not exist then
      7 lines 14-15 in $\mathrm{Opt-BSS}$ (Algorithm 4)
      8 else
      9 if $ |V(H)| \gt |V(H^{\prime})| $ then
      10 $\mathrm{findedH} $.put($\mathrm{mid} $, $ H $);
      11 $ \mathrm{HSet} \leftarrow \mathrm{HSet} \cup \mathrm{RecordBSS} $($ H' $, $ U $, $ D $, $\mathrm{R}$, $ r $, $ \mathrm{count}$, $ q $, $ \mathrm{findedH}$);
      12 lines 19-22 in $\mathrm{Opt-BSS}$ (Algorithm 4)
      13 else
      14 lines 24-25 in $\mathrm{Opt-BSS}$ (Algorithm 4)
      15 return $\mathrm{HSet}$;

      Table 6. 

      $\mathrm{Opt-Record}$.

    • Input: previously discovered community $ H' $, integer $ U \gt 0 $, integer $ D \gt 0 $, ordered list of edge types $\mathrm{R}$, integer $ r \gt 0 $, integer $ \mathrm{count} \geq $ 0, query node $ q $
      Output: SICs with top-$ r $ semantic cohesiveness
      1 $ \mathrm{left} \leftarrow U $; $ \mathrm{right} \leftarrow D $;
      2 $ \mathrm{HSet} \leftarrow \emptyset $; $ \mathrm{SemSet}\_\mathrm{BSS} \leftarrow \emptyset $;
      3 $ \mathrm{lastRight} \leftarrow \emptyset $; $ \mathrm{SemSizeSet} \leftarrow \emptyset $;
      4 while: $ \mathrm{left} \leq \mathrm{right}$ do
      // $ \mathrm{Step (1): Midpoint selection}$
      5 lines 4–11 in $\mathrm{BSS}$ (Algorithm 5)
      // $ \mathrm{Step (2): SIC extraction}$
      6 if $\mathrm{right = D}$ then
      7 $\mathrm{lastH}$ = $\mathrm{findedH}$.get($\mathrm{right}$)
      8 else
      9 $\mathrm{lastH}$ = $\mathrm{findedH}$.get($\mathrm{right + 1}$)
      10 $ H \leftarrow $ find a connected ($ k $,SMP)-core that satisfies $\mathrm{SemSet}\_\mathrm{BSS}$ in $\mathrm{lastH}$ containing $ q $;
      // $ \mathrm{Step (3): SIC refinement}$
      11 if $ H $ exists and $ |V(H)| \gt |V(H^{\prime})| $ then
      12 if $\mathrm{mid}$ = $\mathrm{left}$ then
      13 $\mathrm{count}$ = $\mathrm{count}$ + 1;
      14 lines 16–20 in $\mathrm{BSS}$ (Algorithm 5)
      15 if $\mathrm{left} \gt \mathrm{right}$ then
      16 if $\mathrm{lastRight}$.isEmpty() then
      17 break;
      18 $\mathrm{right} \leftarrow \mathrm{lastRight} $.pop();
      19 else
      20 $ \mathrm{findedH}$.put($\mathrm{mid}$, $ H $);
      21 $\mathrm{lastRight}$.push($\mathrm{right}$);
      22 $\mathrm{right}$ = $\mathrm{mid}-1 $;
      23 $\mathrm{SemSizeSet} \leftarrow \mathrm{SemSizeSet} \cup \mathrm{mid}$
      24 else
      25 $ \mathrm{left}$ = $\mathrm{mid}+1 $;
      26 if $\mathrm{SemSizeSet}$.contains($ \mathrm{mid}+1 $) then
      27 lines 16–18 in $\mathrm{BSS}$ (Algorithm 5)
      28 repeat lines 15–18
      29 return $\mathrm{HSet}$;

      Table 7. 

      $\mathrm{BSS-Record}$($ H' $, $ U $, $ D $, $\mathrm{R}$,$ r $, $\mathrm{count} $,$ q $, $\mathrm{findedH}$).

    • Datasets Nodes Edges Node types Edge types
      Wikidata[41] 3,335,203 10,678,827 12,742 818
      Freebase[42] 3,733,753 10,998,482 3,227 3,897
      YAGO[43] 4,295,825 11,413,472 222,887 149
      DBpedia[10] 7,374,882 22,113,471 432 627

      Table 1. 

      Statistics of datasets.

    • Method Wikidata Freebase
      NMP ALSD SC AAS NMP ALSD SC AAS
      Ours (1)–(6) 34 20.6% 0.844 0.291 34.5 21.5% 0.802 0.186
      $ r $KAC 12.25 55.6% 0.576 0.181 15.5 50.6% 0.649 0.209
      KC 15.7 − 0.413 0.101 21 − 0.294 0.082
      VAC 3.2 − 0.558 0.081 4.5 − 0.504 0.105
      FastOnline 5.3 − − 0.124 13.7 − − 0.163
      Boldface indicates the best result, and underlining indicates the second-best result.

      Table 2. 

      Effectiveness evaluation on Wikidata and Freebase.

    • Method YAGO DBpedia
      NMP ALSD SC AAS NMP ALSD SC AAS
      Ours (1)–(6) 26 16.3% 0.898 0.226 77.75 26.1% 0.877 0.149
      $ r $KAC 11.3 46.6% 0.543 0.128 13.17 73.9% 0.578 0.118
      KC 7 − 0.503 0.115 22.8 − 0.639 0.131
      VAC 2 − 0.524 0.111 2.75 − 0.571 0.116
      FastOnline 8.2 − − 0.142 18.3 − − 0.105
      Red values indicate the best results, while blue underlined values indicate the second-best results.

      Table 3. 

      Effectiveness evaluation for YAGO and DBpedia.

    • Methods Wiki Freebase YAGO DBpedia
      $ G_{\rm{SMP}} $ Other $ G_{\rm{SMP}} $ Other $ G_{\rm{SMP}} $ Other $ G_{\rm{SMP}} $ Other
      Basic 22.38 7.462 21.37 6.028 13.88 3.916 28.86 8.162
      Opt-BSS 15.05 6.665 9.660 4.278 7.770 3.330 19.60 8.460
      Opt-Record 10.44 6.456 4.017 2.483 4.202 2.598 12.36 7.716
      Basic+P 4.940 2.210 16.64 5.256 2.964 0.936 4.560 1.708
      Opt-BSS+P 3.876 1.824 4.148 1.952 1.904 0.896 3.944 1.856
      Opt-Record+P 2.460 1.640 2.880 1.920 0.840 0.560 2.460 1.640

      Table 4. 

      The runtime (sec) of each step.