We consider attribute pattern mining in attributed graphs through recent developments of Formal Concept Analysis. The corresponding methods restrain the extensional space 2O, i.e. the space of possible pattern extensions in the object set O, to a subset satisfying structural properties. When considering an attributed graph, we consider its vertices as the objects under study, each described in a pattern language, as 2I where I is an attribute set. The restriction of the extensional space depends then on the graph topology. We consider two levels. At the global level, the core idea is to reduce the extension of each pattern in such a way that the corresponding abstract extension induces a subgraph made of dense parts whose nodes satisfy some connectivity property. At the local level a pattern has various extensions each associated to one dense part. We obtain that way abstract closed patterns and local closed patterns, together with abstract and local implication rules. Overall, we propose here a way to extract information associated to the attributes labelling the graph vertices, according to its topology. We consider in particular the detection of communities in subgraphs of an attributed network associated to local closed patterns and local implications.
We consider an attributed graph G(O; E) where E is the edge set and whose vertices in
O are labelled by a description in an attribute pattern language with a lattice structure,
typically 2I where I is a set of binary attributes. A way recently investigated to search
for frequent patterns is to define a restricted extensional space which is the range of
an interior operator on 2O(see Section 3). The idea of such an operator in the case of
an attributed graph is to minimally reduce a vertex subset until all the vertices of the
reduced vertex subset, also called an abstract vertex subset, satisfies some connectivity
property within the corresponding induced subgraph[
Recent works in attributed graph mining are interested in searching for local
patterns made of a constraint on a subset of attributes together with a density constraint
on a vertex subset, and this using various notions of maximality [
Both approaches can be mixed by considering the simple graph confluence F mentioned above together with a graph abstraction A. What happens then is that FA = F \A also is a confluence, we call a cc-confluence. In practice, this means that we choose some abstraction A, for instance considering the degree >= k graph abstraction and then consider among its elements only connected vertex subsets. When investigating some attributed graph we have then to chose A, or consider a set of graph abstractions ordered by set theoretic inclusion A1; : : : ; An obtained for instance by increasing k of the degree >= k. As we will see in our experiments, we may extract this way local patterns and implications at different levels.
However connected components of abstract subgraphs as represented in
cc-confluences does not always completely capture the idea of communities as considered in
social network analysis. As discussed in [
GT by the intersection of the corresponding k-clique vertex labels, the local closed pattern associated to the connected component of some pattern subgraph in GT represents the most specific attribute pattern occurring in the corresponding k-community. 4 http://www.stats.ox.ac.uk/˜snijders/siena/s50_data.htm
Section 2 describes the attributed graphs used in our experiments. Section 3 presents abstract concept lattices, abstract implications and graph abstractions. Section 4 defines local concept pre-confluences, related local implications and cc-confluences. In Section 5 we show how using derived c-confluences we extract the set of 3-communities associated to pattern subgraphs, and we display the local concept pre-confluence of the teenage friendship attributed network displayed Figure 1. In Section 6 we briefly discuss the implementation used in our experiments. 2
We will further consider experiments in two datasets. In both cases the data is described as a graph G = (O; E) whose vertices have as labels elements of 2I where I is a set of items, i.e. binary attributes. As objects are not always described using binary attributes, the binarization preprocessing is described when necessary. 2.1
The dataset is denoted as s50-1 and is a standard attributed graph dataset5. It represents 148 friendship relations between 50 pupils of a school in the West of Scotland, and labels concern the substance use (tobacco, cannabis and alcohol) and sporting activity. Values of the corresponding variables are ordered. The binarization process consists in defining variables representing the value intervals. T stands for Tobacco consumption and has values 1 (no smoking), 2 (occasional) and 3 (regular). C stands for cannabis consumption and has values 1 (never tries) to 4, D stands for alcohol consumption and has values 1 (does not drink) to 5, and S stands for sporting activity and has two values 1 (occasional) and (2) regular. A binary variable represents an interval, as for instance C23 that has value 1 whenever the value of C is in [2; 3]. For sake of simplicity we have merged the two highest values in variables T,C and D. For instance values 4 and 5 in alcohol consumption are merged into a 4m (4 and more) value. We report hereunder the binary attributes whose conjunctions allow to represent any interval (for instance D=2 is obtained as fD12,D23mg):
Tobacco Cannabis Alcohol
T1,T2m C1,C12,C23m,C3m D1,D12,D123,D23m,D34m,D4m 2.2
This is the DBLP dataset as described in [
The binary attributes are the journal and conference names together with the three clusters. An attribute has value 1 if the author has published in the corresponding journal or conference or cluster. 3 3.1
A standard pattern mining consists in considering the set of occurrences of a pattern q, belonging to some pattern language L with a lattice structure 8, as a subset of an object set O. This language is partially ordered following a general-to-specific ordering and each object o is described as a particular pattern d(o). A pattern q occurs in object o whenever d(o) is less specific than q. The set of occurrences ext(q) of a pattern q is called its support set or its extension in O. A pattern q is said support-closed whenever it is a maximal pattern (i.e. maximally specific) among those that are equivalent in what they share the same support set as q. Now, whenever there is a unique support closed pattern corresponding to a given support set e, as it is the case in the standard FCA or itemset mining framework, an intension function int(e) returns the support-closed pattern associated to the support set e. This means that we relate a pattern q to the corresponding support closed pattern by applying the closure operator int ext to q. The pattern language L typically is 2I where I is a set of binary attributes (aka items). With no loss of generality we will further use such a pattern language. The closure operator then simply intersects the object descriptions of the support set of the entry pattern.
The set of frequent support closed patterns, i.e. the support-closed elements with
support greater than or equal to some threshold minsupp represents then all the
equivalence classes corresponding to frequent supports. Such a class has also minimal
elements, called generators. When the patterns belong to 2X , the min-max basis of
implication rules[
In the first case, an element such that x = f (x) is called a closed element.
Ranges of interior operators on lattices are called abstractions and are characterized
by the following Proposition:
Proposition 1 (see [
p(x) = supfa2Aja xga.
Let then p be the interior operator associated to some abstraction A, p(x) is the
greatest element of A included in x. Closed pattern analysis has been recently extended to
abstract closed pattern analysis by noticing that applying an interior operator on the
extensional space 2O we obtain again closure operators on the pattern language 2I [
The abstract support set of pattern q is defined as p ext(q). There is then a unique
abstract support closed pattern, i.e. a most specific pattern among all patterns sharing
the same abstract support set, which is obtained as f (q) = int p ext(q). f (q) is
then called an abstract closed pattern. This leads to the definition of abstract concepts
organized in a concept lattice:
Corollary 1 [
Note that, as p is monotone, whenever ext(q) ext(w), i.e. q ! w is valid we also have extA(p) = p ext(q) extA(w) = p ext(w), i.e. the abstract implication 2Aq ! 2Aw is also valid.
This way we obtain abstract min-max basis with the same definition as in section 3.1 except that extA replaces ext and therefore abstract implications relate minimal elements (i.e. A-generators) to maximal element (the abstract closed pattern, or A-closed pattern) of the same abstract equivalence class. We have then the following definition: Definition 2 The abstract min-max basis mA of valid abstract implications is defined as
mA = f2Ag ! 2Af ng j f is an A-closed pattern; g is a A-generator ; f 6= g; extA(g) = extA(f )g 3.2
These ideas has been applied to attributed graphs by defining graph abstractions [
The set of objects O is then the set of vertices of a graph G = (O; E) and each vertex o is labelled by an attribute pattern d(o) 2 2I .
A graph abstraction is an abstraction of 2Odefined through a characteristic property P (x; e) which expresses some minimal connectivity requirement of the vertex x within the subgraph Ge induced by some vertex subset e: Lemma 1 Let P be such that – P (x; e) implies x 2 e and – e e0 and P (x; e) implies P (x; e0), and let q be a mapping defined by q(e) = fx 2 ejP (x; e)g, then the mapping p defined by p(e) = xedpoint(q; e) is an interior operator on 2O
p(e) represents the greatest vertex subset of e inducing a subgraph whose vertices
all satisfy the associated characteristic property. We give hereunder examples of graph
abstractions, defined through their characteristic property and exemplified in Figure 2.
1. degree k.
2. k-club s: x has to belong to at least one k-club of size at least s in Ge. This
is a relaxation of the notion of clique[
Figure 2-d).
5. k-cliqueGroup s: x has to belong to a k-clique group of size at least s. A
kclique group is a union of k-vertex cliques that can be reached from each other
through a series of adjacent k-vertex cliques (where adjacency means sharing k
- 1 nodes). Maximal k-clique groups are denoted as k-cliques communities and
formalize the idea of community in complex networks [
Finally, it is interesting to note that we can combine two (or more) abstractions A1 and A2 in two ways, defining a new composite abstraction either stronger or weaker than both A1 and A2. For instance, we may want to consider an abstract subgraph where vertices both have a degree larger than some k and belong to a connected component exceeding a minimal size s. On the contrary, we may want an abstract subgraph such that at least one of the two characteristic properties is satisfied by all the vertices. This would be the case for instance, if we want to keep both vertices that have a degree larger than, say 10, and vertices in a star, i.e connected to a hub which degree is at least 50.
The following lemma states that we can freely combine abstractions in both directions.
high degree vertices) together with their (low degree) neighbors (see Figure 2-c). 4. cc s: x has to belong to a connected component of size at least
s in Ge (see Figure 2-d). 5. k-cliqueGroup s: x has to belong to a k-clique group of size at least s. A k-clique group is a union of k-cliques (cliques of size k) that can be reached from each other through a series of adjacent k-cliques (where adjacency means sharing k - 1 nodes).
Maximal k-cliques groups are denoted as k-cliques communities
and formalize the idea of community in complex networks [
⇥ (a) ⇥ (b)
⇥ (c) ⇥ ⇥
⇥ (d) and abstract closures int p ext(t). All top-down generate and clo algorithms, like LCM [16] can then be adapted to direct computati of abstract closed patterns4. In the experiments in the next section have used an indirect approach: we first compute frequent closed p terns and corresponding generators using the CORON software[1 Starting from the closed patterns t and their supports, we then co pute the abstract closed patterns int p ext(t). Finally we consi for each abstract closed pattern tA the generators of all the closed p terns that have produced tA and select the minimal elements amo them in order to obtain the corresponding abstract generators5. Fr abstract generators and abstract closed terms, computing the mi max implication rule basis is straightforward. On one hand, the i direct approach needs prior computation of the (non abstract) clos patterns, and this can be much more costly than the direct comp tation of abstract closed patterns. On the other hand, once this fi computation is performed, we can apply as many abstract compu tions we need, varying graph abstractions and their parameters, a this can be cost-saving when investigating some new large attribut graph (see Section 4.3).
We describe hereunder a generic algorithm, relying on the abstr want an abstract subgraph such that at least one of the two charac– P1 ^ P2(x; e)teristic properties is Psa2ti(sfixe;deb)y all the vertices. This would be the
= P1(x; e) case for instance, ^if we want to keep both vertices that have a degree – P1 _ P2(x; e)lar=gerPth1a(nx,s;aye)10_,anPd2v(erxti;cees)in a star, i.e connected to a hub which degree is at least 50. The following lemma states that we can freely This generic algorithm is in O(n2 ⇤ d) where d is the cost of co combine abstractions in both directions. puting P (x, e0). In the graph abstraction case, computing P (x, Both P1 ^ P2 and P1 _ P2 are characteristic properties of abstractionsr.equires to update the induced subgraph Ge0 when some vertex is Lemma 2 Let P1 and P2 two characteristic properties of abstrac- moved from e0. Furthermore, the cost d depends on the characteris tions defined on the same object set O, and let P1 ^ P2 and P1 _ P2 property and will be small as far as the property needs to consi be defined as follows: only close neighbors of x. For instance, considering the degree 3.3 Experiments abstraction, first, there is no need to access neighbors of x, and f • P1 ^ P2(x, e) = P1(x, e) ^ P2(x, e) thermore, rather than explicitly updating Ge0 when some x is • P1 _ P2(x, e) = P1(x, e) _ P2(x, e) moved from e0 it is more efficient to decrease the degree of the v Some experimentBsotohnP1t^heP2twanod Pd1a_ taPs2eatsre dcheasrcacrtiebriesdtic ipnropSeertcietsioofnab2strhaca-ve btieceesncopnenercftoedr mtoexdin e0. Another example is the cc s graph a and presented in [ti1o]n.s.We discuss here some new details and experimentsstraoctnionth,ien wDhBichLcPomputing the abstraction of some e comes do dataset. The experiment consisted in applying a degree k abstraction twociothmpinutcerteheascionnngected components of Ge and remove the sm
Finally note that requiring a frequency property also corresponds ones with no need to iterate the process. k-values and we ftoocaunsasbestdracitnionabwshtorsaeccthapraacttteerirsntisc porboptearitny eisdPwm(ixth,ek)==|e1|6 which corresponds to a very strong ambisntsruapcpt,ioannd: tihnatacnanabbestthrearceftorseucpopmobrintesdetto eanaychabasturatchtioonr, is re4quEirxepdertoimheanvtes
therefore defining frequent abstract closed patterns. 16 co-authors within the abstract support set. We obtained few abstractWcelocosnesdideprahtetreersnosme preliminary experiments in three datasets. and in particular the abstract closed pattern VLDBJ; ICDE; SIGMOD;aVlltLhrDeeBexpaenridmtehntes, the data is described as a graph G = (O, 3.2 Graph-based closed patterns computation and related abstract implicaantiaolnys2is VLDBJ ! 2 ICDE; SIGMOD; VLD B4W.oBrkointhprotghreessabstract closed patteWrhnenawnedhaitvse daebfisnterdaacbtstrgaectnioenrsaatnodr cVorrLesDpoBndJinghparvojeectaionnsa,bstr5aRcetcaslluthpapteoacrht csloesetd pattern that produces an abstract closed pattern represents an equivalence class of patterns that will be included in the cl of 38 among the g1ra2p7h-6basVedLaDbstBracJt caloustehdopratsterinns atrheealsdoadteafsaectto. dTefihneedi.mUspinlgicationof tsAtaintethse ntehwaetquaivalence relation relying on abstract supports. endFor endWhile // As u = false, P (x, e0) is true for all x in e0 // e0 = p(e0) is the abstraction of e with respect to P dense group of co-authors that have published in the Very Large Database Journal also have published in several database conferences. We present Figure 3 the corresponding subgraph. Such a very dense co-authoring subgraph within the VLDBJ subgraph is somewhat unexpected. We made then some investigations in the DBLP repository, focussing of these authors, and found an article whose abstract begins as follows:
A group of senior database researchers gathers every few years to assess the state of database research ...
with the following reference: dblp: Serge Abiteboul
[c128] 2005 [j56]
Entrepôts de contenu autour de XML et des services Web.
EDA 2006: 1-2 Serge Abiteboul, Ioana Manolescu, Emanuel Taropa: A Framework for Distributed XML Data Management. EDBT 2006: 1049-1058 [j55]
Yannis E. Ioannidis, David Maier, Serge Abiteboul, Peter Buneman, In some sense the exSpulsaannaBt.ioDnavoidfstohne, EpdawttaerrdnAw.Feoxd, iAslcoonvYe.rHeadleivsy,sCtrraaiiggAh.tforward. How
Knoblock, Fausto Rabitti, Hans-Jörg Schek, Gerhard Weikum: ever, the whole purposeDoigfital library information-technology infrastpruatctteurrness,. Ihnitd.Jd.en within
pattern mining is to find unexpected large datasets, and interponreDtigthitealmLibinraorierdse5r(4t)o:2a6c6q-2u7i4r e(2s0o05m) e new knowledge. It is exactly what happens here: we were not aware of these regular meetings of senior database re
[j54] Serge Abiteboul, Richard Hull, Victor Vianu, Sheila A. Greibach, searchers, and we learned something new, though, of course, this
Michael A. Harrison, Ellis Horowitz, Daniel J. Rosenkkrannotwz, lJeeffdrgeey is clearly widely known within thDe. dUalltmaabna,sMeocsohmeYm.Vuanrditiy:.
When considering aInwmeaekmeorryabosftSreaycmtioounr, Gnianmsbeulyrgh1e9r2e8 a-2d0e04g.rSeIeGMOD4 Raebcsotrrdaction, we obtain more abstract clo3s4e(d1):p5a-t1t2er(2n0s0s5o)metimes made of several connected components.
Figure 4[jr5e3p]resents the TDovMaMKilDo,;SIeDrgAeArbeivtebpoauttl,eBrnernsdubAgmraanpnh, OtomgaertBheenrjewlloituhn,the subgraph induced by the abstract sFruepdpeorirctDsaentgoNfgtohce: pattern. This abstract subgraph is made of two connected components,Etxhcehoanngeining itnhteenrisgiohntaplaXrMtoLfdtahtea.FAiCgMurTerainssm.Daadtaeboasfe1S0ysvt.ertices and
30(1): 1-40 (2005) we are then interested in knowing whether there is some more specific pattern than the abstract [ccl1o2s5e]d pattern DSMerKgeDAb;iIteDbAourle,SvuwsahniBc.hDwavoiduslodnb,TeovsahaMrielod: by this connected component. Answering suchAqctuiveestXioMnLsamndeDanastamAcintiivnagtioant.aAblostcraacltlSetvateel Mthaechaintetrsib20u0te5:d graph,
11-16 and this is the subject of the next section.
http://dblp.uni-trier.de/pers/hd/a/Abiteboul:Serge
In [
First note that partial orders considered here are all finite. We first define a preconfluence as an ordered structures that generalize the lattice structure: Definition 3 F is a pre-confluence if and only if for any m 2 min(F ), F m = fx 2 F j x mg is a lattice.
A consequence of this definition is that a (finite) lattice is a pre-confluence with a minimum. The structure has a partial join operator: Lemma 3 For any x; y 2 F m their least upper bound does not depend on m: 1. x _F y is the least element of F x \ F y
This means that a pre-confluence is a union of lattices in which joins coincide. A particular case is which of a pre-confluence included in a host lattice and which is join preserving: Definition 4 Let T be a lattice and F F is called a confluence of T .
T be a pre-confluence with as join _F = _T , An abstraction of T , as defined above is a confluence of T with ?T as minimum. We have then the following property when considering 2O as the host lattice: Proposition 3 Let X = 2O be a lattice, F X is a confluence of X if and only if for any x; y 2 F m with m 2 min(F ), we have that x [ y belongs to F .
A confluence, is then associated to a set of interior operators: Proposition 4 Let F be a confluence of a lattice X, and m 2 min(F ), – pm : Xm ! Xm, such that pm(x) = _q2F m\Xx q, is an interior operator and pm[Xm] = F m.
We are concerned here with extensional confluences, i.e. confluences of X = 2O[
1 1 2 1 2 1 4 2
3 4 1 2 3 1 2 1 4 3 4 3 2 3 4 3 4 3
Example 1. Let G = (O; E) be a graph (displayed at the bottom of Figure 5) whose vertex set is O = f1; 2; 3; 4g. Let F 2O be the set of vertex subsets inducing connected subgraphs of G. We call them connected vertex subsets. F is a confluence whose set of minimal elements is min(F ) = ff1g; f2g; f3g; f4gg, i.e. the set of singletons of 2O. The union of two connected vertex subsets that each contains a given vertex s obviously also is a connected vertex subsets and therefore F is a confluence of 2O. In what follows, by abuse of notation we write ps and F s rather than pfsg and F fsg.The interior operator ps projects then any vertex subset e containing vertex s on the connected component of the subgraph Ge induced by e that contains s. The up set F s is then the set of connected vertex subsets containing s and the union of all these F s represents the whole set of connected subgraphs of G. The subset F 1+3 = F 1 [ F 3 representing connected vertex subsets containing vertices 1 or 3 also is a confluence. Figure 5 displays the diagram of F 1+3. 2
The support set e of a pattern q may then be projected, through interior operators,
on various smaller local support sets feig corresponding, in the graph confluence case,
to the connected components of the pattern subgraph. These interior operators are
associated to local closure operators[
In the graph confluence case, let e = ext(q), ps(e) is the connected component of the pattern subgraph Ge to which belongs the vertex s. Obviously ps(e) = pv(e) for any vertex v in the same connected component. Therefore fs(q) is a local closed pattern w.r.t. any vertex in this connected component, i.e. the most specific pattern shared by the vertices in the connected component.
Now an important result is that that the set of local support sets is a pre-confluence: Theorem 1. The mapping h : F ! F : h(e) = pm ext int(e) for m is a closure operator on F and E = h[F ] is a pre-confluence. e h(e) is therefore the local support set of int(e) that contains m e. h[F ] is a pre-confluence isomorphic to the set P of local concept pairs defined as follows: Definition 5 The set of local concept pairs P = f(e; l) j e = pm int(e); m eg is called a local concept pre-confluence. ext(l); l =
To summarize we have defined local concepts as (local support set, local closed patterns) pairs and shown they were organized in a structure with possibly several minimal elements, therefore generalizing the concept lattice definition. In the simple graph confluence exemplified above the local support sets simply are the connected components of the pattern subgraphs. We will now extend graph confluences by intersecting this simple graph confluence with abstractions. 4.1
We remark now that we can freely intersect confluences: Proposition 6 Let F1 and F2 be confluences of X, then F1 \ F2 is a confluence
And as abstractions of X are confluences of X with the bottom element of X as their unique minimal element, the above proposition means we can freely intersect abstractions with confluences to build smaller confluences. Many confluences can then be derived from a graph confluence by intersecting it with some abstractions. We call this family of confluences the cc-confluences. For instance, considering A as the kclique abstraction, we obtain the cc-confluence of connected subgraphs of G made of k-cliques. Note that cc-confluences have an important property: rather than considering the minimal elements of F when defining local closure operators we can consider vertices. This is because given a vertex subset v in some pattern subgraph, all minimal elements containing v belong to the same connected component as v, and therefore the local support sets are the same. This is computationally important as this means that when considering local support sets we only need to consider each vertex in the support set and associate it to the connected component to which it belongs. Inclusion of local support sets define local implication rules 2mq ! 2mw where m is a minimal element of FA in the support set of q. Note that, as the local support set of pattern q is obtained by applying an interior operator, which is monotone, to the support set of q, we have that whenever 2q ! 2w is valid and m extA(w), we also have that 2mq ! 2mw is valid, i.e. we may infer the latter local rule from the former abstract rule.
We search now for a basis B of valid local implication rules from which we may infer any local implication rules. We will consider a basis Bm for a given minimal element m of F and obtain the whole basis B = [Bm by joining these bases. Consider a given abstract closed pattern c whose abstract support set has a connected component that contains m, and let l = fm(c) be the corresponding local closed pattern, with respect to the cc-confluence FA. We have then that the implication rule 2mc ! 2ml holds. We select then a basis Bm of informative (l 6= c) and irredundant ( there is no other rule 2mc0 ! 2ml with c0 less specific than c in the rule set) ones. From Bm we may infer all local implication rules associated to m by applying standard axioms in the same way as in the case of the min-max basis in the standard closed or abstract framework. The basis B = [Bm represents the local knowledge deriving from the reduction of the extensional space from abstraction A to cc-confluence FA. 4.3
To shortly examplifiy local implications and local concepts we come back to our experiments on the DBLP dataset in Section 3.3 and specifically the abstract closed pattern DMKD; IDArev, with respect to the degree 4 abstraction, whose abstract support set is represented in red on Figure 4. When considering the connected component on the left of FIgure 4, we obtain the local implication DMKD,IDArev !268924 DMgroup stating that in the connected component of the abstract subgraph to which belongs the author 268924, each author has also published in some data mining conference belonging to DMgroup.
Now, when considering the Teenage Friends attributed graph displayed Figure 1, clearly the friendship relations are organized in 3-cliques, therefore any stronger abstraction will be poorly informative. However, as mentioned in Section 1, when considering the 3-clique abstract graph associated to the empty pattern the unique connected component could be separated in several (overlapping) communities (displayed in various colors). We discuss and exemplify in the next section how to apply the local closure strategy to discover such subcommunities in an attributed graph.
In what follows, we will consider a family T 2O of vertex subsets, and consider T as
the vertex set of a graph GT = (T; ET ) derived from G. The simple graph confluence
F of 2T is then the new extensional space and we will search for the corresponding local
closed patterns. The local support sets are afterwards transformed into support sets in
2O. Let u : 2T ! 2O be such that u(eT ) = [t2eT t. u(eT ) is called the flattening of
eT . We consider then the two maps extT and intT defined as follows:
– extT : L ! 2T with extT (q) = ftjt ext(q)g
– intT : 2T ! L with intT (eT ) = int u(eT )
extT (q) represents the support set of q in T when considering that q occurs in t
whenever q occurs in all elements of t (seen as a subset of O). Conversely intT (eT ) represents
the greatest pattern in L whose support set in T includes eT , i.e. whose support set in O
contains, as subsets, the elements of eT . Now, consider as T the family of k-cliques of
G and that (t1; t2) 2 ET whenever t1 and t2 share k 1 vertices in G. A k-community
in G [
Coming back to our Teenage Friendship attributed graph, we have applied this strategy and built the derived graph GT where T is the set of 3-cliques of the original attributed graph. We display Figures 6 and 7 the local concept pre-confluence of 3-communities which size is greater than or equal to 4 members9. The minimal 3-communities are the lowest ones on both Figures. Each element of the pre-confluence represents a (3community, local closed pattern) pair but may be associated to several non redundant local implications. This happens for one 3-community displayed on the right at the bottom of Figure 6 and associated to two local implications each represented in a square. Each square displays in red the 3-community, and in red+green+blue the abstract support set of the abstract closed pattern forming the left part of the implication. In Figure 7 we have a unique maximal 3-community on the top, and a hierarchy of sub-communities.
In our experiments we use the CORON software[15] to compute frequent closed patterns, according to some frequency threshold, then apply a set of PYTHON functions 9 Formally, this means that we also apply to the derived graph an abstraction to avoid connected components corresponding to 3-communities smaller than 4 members. file:///Users/soldano/Dropbox/rangementsAutres/softGuillau...
file:///Users/soldano/Dropb 4 3-communities of the Teenage Friendship graph(part-I) file:///Users/soldano/Dropbox/rangement
Fig. 7. The pre-confluence of size 1 of 1 as a post processing10. Starting from the set of frequent (possibly abstract) closed patterns C we then compute for each such pattern c 2 C the subgraph induced by its (abstract) support set, extract the various connected components fe1; :::; ekg that are large enough, compute the corresponding local closed patterns fc1; :::; ckg and output the corresponding local implications. When computing k-communities, we start from the k-clique graph abstract closed and build the k-clique graph GT , where T is the set of k-cliques in G, compute the local closures corresponding to the subgraphs of GT induced by the connected components of our abstract closed patterns, and output the corresponding triples, where the local support sets are flattened to be expressed as subsets of O.
In a work in progress, we consider a more efficient computation of abstract and local
closed patterns and related implications. The corresponding algorithm uses a divide and
conquer strategy similar to that proposed in [
In the present article we are interested in addressing problems in which the extensional
space, made of the vertex subsets of an attributed network, is constrained according
to connectivity properties. We have first considered abstract vertex subsets in which a
constraint have to be satisfied by each vertex in the subgraph they induce, as for instance
a minimum degree constraint. The extensional space is in this case a particular lattice
called an abstraction. We have then shown, benefiting from previous work in FCA, how
abstract support closed patterns, i.e. maximal patterns among those sharing the same
abstract support set, could be obtained using a closure operator. This led to define a
wide class of abstract concept lattices, whose elements are (abstract support set, abstract
closed pattern) pairs, each corresponding to a particular abstraction. We obtain this way
a global information on how the graph topology is related to the patterns support sets.
We have then considered a way to extract local knowledge from an attributed network.
For that purpose, using a recent extension of FCA to local extensional spaces, called
confluences, we have related each pattern to various local support sets, corresponding
to connected components in subgraphs induced by abstract vertex subsets. We obtain
this way a set of local concepts, organized in a generalization of the lattice structure
called a pre-confluence. Furthermore we have defined both abstract implications and
local implications rules representing knowledge which is valid at the abstract and local
levels, i.e., regarding the latter, in the vicinity of particular vertices. Finally we have
applied these ideas to define the pre-confluence of 3-communities in a social network.
These 3-communities are in fact sub-communities as each is a 3-community in some
subnetwork induced by an attribute pattern. Overall, what we propose here is a new
way, brought by recent developments in Formal Concept Analysis, to explore social
networks as attributed graphs. Future works concerns, on the extensional side, applying
these ideas to attributed directed graphs or multiplex networks. We also consider to
use abstract and local extensional constraints while extending the pattern language to a
10 The corresponding software is to be found in https://lipn.univ-paris13.fr/
˜santini/ .
wider class of pattern languages. First, as in [