Dear all,

I need to calculate the sum of =
the weights
along all paths from each of n-1vertices to a target vertex in a =
graph.

Example:

mat=3Dmatrix(c(rep(0,6),3,0,2,rep(0,3),4,rep(0,2),2,rep(0,6)=
,rep(1,2),rep(0,2),3,rep(0,9)),byrow=3DT,ncol=3D6)

graph =3D graph.adjacency(mat,
mode=3D"directed", weighted=3DTRUE)#do =
graph

plot.igraph(graph,edge.label=3DE(graph)$weight)

Assuming that vertex 1 is the =
target, the
sum of the weights (sw) along the paths from every other vertex in the =
graph should
be:

sw_{V2} =3D =
3+2+4

sw_{V3} =3D =
4

sw_{V4} =3D =
1+3+4

sw_{V5} =3D =
3+4

sw_{V6} =3D =
0

Note that, in identifying all =
paths from a
vertex to the target, only paths have been considered in which a vertex =
is
traversed only once along the same path. This applies to vertex 5, for
instance, where the sum of weights disregards the weights present in the =
cycle
with vertices 3 and 4.

I would appreciate any advice =
about how
this could be achieved. Thanks in advance,

Sofia

Hello,

) id 1Vna2w-0007bK-St
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:24:52 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vna2r-0007Vt-3Q
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:24:46 -0500
Received: from mail-bk0-x22b.google.com ([2a00:1450:4008:c01::22b]:54981)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vna2q-0007Vh-QF
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:24:41 -0500
Received: by mail-bk0-f43.google.com with SMTP id mz12so5590970bkb.2
for ; Mon, 02 Dec 2013 12:24:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=date:from:to:message-id:in-reply-to:references:subject:mime-version
:content-type:content-transfer-encoding:content-disposition;
bh=pIYC4It9BCHaeoGgeod9YuBRnD5Y4vG1Qw5aatxpP6U=;
b=JC9BN2jHCdA2TRWNjUbZVAFnDToBH1+nD+cJWCCgYPGdx0d8qJAVcLjZ6y8vtSTaUT
PIX8q7XxScm8Nfzjn8ErbQwbEhSeLiuTYk53K0XIg4CQ4VMj08b1i2PlwbuTJAFmVwL/
wOk9amzLDIVXBemxsDLho6G0lozGBMI4nOmlGq6Pob2hCwwxJZHJaNywqZ7eOCIMTsw4
PLcAJHHeimYVNPDXoXU0iVib1F7TL1GJHEsuzj/Mx5podiWJSobJ22yV6iYPBYlKdouU
Bnjv/WR6wL+GRPkMdOq6EEj2ft5Muqaq0pl+jSQJYMJoU0VQ6SUtKgvdCLepvBkciQDc
DQQg==
X-Received: by 10.204.100.193 with SMTP id z1mr726640bkn.53.1386015879481;
Mon, 02 Dec 2013 12:24:39 -0800 (PST)
Received: from [192.168.1.3] (BC240C53.catv.pool.telekom.hu. [188.36.12.83])
by mx.google.com with ESMTPSA id z6sm76032999bkn.8.2013.12.02.12.24.38
for
(version=TLSv1 cipher=RC4-SHA bits=128/128);
Mon, 02 Dec 2013 12:24:38 -0800 (PST)
Date: Mon, 2 Dec 2013 21:24:37 +0100
From: =?utf-8?Q?Tam=C3=A1s_Nepusz?=
To: Help for igraph users
Message-ID: <3F15F50339264E6A85499F7F20FD6F94@gmail.com>
In-Reply-To:
References:
X-Mailer: sparrow 1.6.4 (build 1178)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2a00:1450:4008:c01::22b
Subject: Re: [igraph] Blissigraph_canonical_permutation()
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 02 Dec 2013 20:24:52 -0000
Hello, =20
There isn=E2=80=99t, unfortunately. I have accidentally skipped this func=
tion while creating the Python wrapper. I=E2=80=99ll add it soon. =20
All the best,
-- =20
T.
On Monday, 2 December 2013 at 21:19, =46rank Imeson wrote:
> Hello,
> =20
> Does anyone know if there a similar method to Blissigraph=5Fcanonical=5F=
permutation() in the python library=3F
> =20
> Thanks
> - =46rank
> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=
=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F
> igraph-help mailing list
> igraph-help=40nongnu.org (mailto:igraph-help=40nongnu.org)
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Mon Dec 02 15:30:14 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vna8E-0001aJ-JB
for mharc-igraph-help@gnu.org; Mon, 02 Dec 2013 15:30:14 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:35117)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vna8B-0001Ww-Fp
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:30:12 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vna8A-0001FM-Df
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:30:11 -0500
Received: from mail-oa0-x22a.google.com ([2607:f8b0:4003:c02::22a]:34264)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vna8A-0001FG-7w
for igraph-help@nongnu.org; Mon, 02 Dec 2013 15:30:10 -0500
Received: by mail-oa0-f42.google.com with SMTP id i4so13980401oah.29
for ; Mon, 02 Dec 2013 12:30:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to:cc:content-type;
bh=irxsZsnXgAScbzcy4tr0j8o0s1dSV2sQMKvxs9+QQTw=;
b=G/Ltd/0kxhSlrmHLh8shM6EMS9+3iN5aStLLw/8PAtfVNIx4q3GZKN+LlMllgP14/n
bdiekIrLRAVETiAhNE+T16k3DFFcPqu6kSEh3FjZr1cmFyEKE45I2lHGQBvysMECw7tY
D5qZSu24EahC1CZNaicQscUc0AqYPHQMVaHjG9iR46EIuU55EgLReor8vC8nCz8C7MLc
wp+B6U+k/xi7Hd0citU+de4buIrRShmNyZXJLA+sTD/9tbQyH/cUX8pzsulYu/ZpH1qa
3eisiriS/2k/O7HtqRp23qdAqCVR/qhnJ2pzmore83Jppc26XlVP5bh6bkPQZ5mxHH0k
/bOg==
MIME-Version: 1.0
X-Received: by 10.182.230.135 with SMTP id sy7mr55820951obc.24.1386016209174;
Mon, 02 Dec 2013 12:30:09 -0800 (PST)
Received: by 10.60.44.37 with HTTP; Mon, 2 Dec 2013 12:30:09 -0800 (PST)
Date: Mon, 2 Dec 2013 15:30:09 -0500
Message-ID:
From: Matthew Galati
To: Help for igraph users
Content-Type: multipart/alternative; boundary=001a11c33676cd066004ec930b33
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:4003:c02::22a
Subject: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 02 Dec 2013 20:30:12 -0000
--001a11c33676cd066004ec930b33
Content-Type: text/plain; charset=ISO-8859-1
I am considering this small directed graph.
The results score node 1 as the dominate hub and the rest of the nodes with
value 0 (i.e., no' hubness'). This seems odd to me. For example, node 2,
has outlinks to 3 different nodes (1,4, and 7). So, I would expect it to
have some relative level of hubness.
> g <- graph.empty()
> g <- g+vertices(1,2,3,4,5,6,7)
> g <- g+edge("1","2")
> g <- g+edge("1","3")
> g <- g+edge("1","5")
> g <- g+edge("1","6")
> g <- g+edge("2","1")
> g <- g+edge("2","4")
> g <- g+edge("3","1")
> g <- g+edge("5","1")
> g <- g+edge("2","7")
> E(g)
Edge sequence:
[1] 1 -> 2
[2] 1 -> 3
[3] 1 -> 5
[4] 1 -> 6
[5] 2 -> 1
[6] 2 -> 4
[7] 3 -> 1
[8] 5 -> 1
[9] 2 -> 7
> hub.score(g,scale=FALSE)$vector
1 2 3 4 5 6 7
0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000
--001a11c33676cd066004ec930b33
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

--001a11c33676cd066004ec930b33--
From MAILER-DAEMON Mon Dec 02 17:15:29 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vnbm5-0004tY-Gd
for mharc-igraph-help@gnu.org; Mon, 02 Dec 2013 17:15:29 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:60073)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnblx-0004qN-0b
for igraph-help@nongnu.org; Mon, 02 Dec 2013 17:15:26 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vnblq-0001Ga-QZ
for igraph-help@nongnu.org; Mon, 02 Dec 2013 17:15:20 -0500
Received: from mail-bk0-x22e.google.com ([2a00:1450:4008:c01::22e]:59569)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnblq-0001GK-FI
for igraph-help@nongnu.org; Mon, 02 Dec 2013 17:15:14 -0500
Received: by mail-bk0-f46.google.com with SMTP id u15so5705063bkz.33
for ; Mon, 02 Dec 2013 14:15:13 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=date:from:to:message-id:in-reply-to:references:subject:mime-version
:content-type:content-transfer-encoding:content-disposition;
bh=TF9daIWDiY/4l/hnxRxkzmjsbj4cQJyR82b0A6HUxo0=;
b=qnP2B0uwsnZLNO83XFbxuxbijNK9ewZkJQQ8IiwavR/Ex2VNBhOMvSuhSaO26ZIYWi
oWwY44RxPSyFMJtBR97JED39vhKGz25svKplw35cUbSFUAdMdDpmXUO/MoEwNvWBrv1p
c6IqNv1rLlyVBq2r4ZLCXtAX3nUU2Cqm5xUwmP4NmozCACXlksSDU/Sc2loMrfvhfbl9
3I7S4nBCvhbjaosfvOJ6TDqxTksJQw9HWDIXRZjJsKhmrvAl1UCwt1T8W8nFEJqFVm3r
nGCtsOAfZ2K50SxTjizwcqPqA2O6XxJwQGXGPW3pwYjtCmJbMuq+yzWl7QNN94Bpbl9L
q5vQ==
X-Received: by 10.204.166.15 with SMTP id k15mr47991bky.78.1386022513455;
Mon, 02 Dec 2013 14:15:13 -0800 (PST)
Received: from [192.168.1.3] (BC240C53.catv.pool.telekom.hu. [188.36.12.83])
by mx.google.com with ESMTPSA id qe6sm76277056bkb.5.2013.12.02.14.15.12
for
(version=TLSv1 cipher=RC4-SHA bits=128/128);
Mon, 02 Dec 2013 14:15:13 -0800 (PST)
Date: Mon, 2 Dec 2013 23:15:11 +0100
From: =?utf-8?Q?Tam=C3=A1s_Nepusz?=
To: Help for igraph users
Message-ID:
In-Reply-To:
References:
X-Mailer: sparrow 1.6.4 (build 1178)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2a00:1450:4008:c01::22e
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 02 Dec 2013 22:15:27 -0000
Hi Matthew, =20
Yes, that=E2=80=99s odd indeed. Let me double-check our code; I suspect a=
n ARPACK convergence problem here but I=E2=80=99m not sure (and I don=E2=80=
=99t know why there=E2=80=99s no warning if ARPACK indeed fails to conver=
ge). =20
-- =20
T.
On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
> I am considering this small directed graph. =20
> =20
> The results score node 1 as the dominate hub and the rest of the nodes =
with value 0 (i.e., no' hubness'). This seems odd to me. =46or example, n=
ode 2, has outlinks to 3 different nodes (1,4, and 7). So, I would expect=
it to have some relative level of hubness. =20
> =20
> > g <- graph.empty() =20
> > g <- g+vertices(1,2,3,4,5,6,7)
> > g <- g+edge(=221=22,=222=22)
> > g <- g+edge(=221=22,=223=22)
> > g <- g+edge(=221=22,=225=22)
> > g <- g+edge(=221=22,=226=22)
> > g <- g+edge(=222=22,=221=22)
> > g <- g+edge(=222=22,=224=22)
> > g <- g+edge(=223=22,=221=22)
> > g <- g+edge(=225=22,=221=22)
> > g <- g+edge(=222=22,=227=22)
> > E(g)
> =20
> Edge sequence:
> =20
> =5B1=5D 1 -> 2
> =5B2=5D 1 -> 3
> =5B3=5D 1 -> 5
> =5B4=5D 1 -> 6
> =5B5=5D 2 -> 1
> =5B6=5D 2 -> 4
> =5B7=5D 3 -> 1
> =5B8=5D 5 -> 1
> =5B9=5D 2 -> 7
> =20
> > hub.score(g,scale=3D=46ALSE)=24vector
> =20
> 1 2 3 4 5 6 7 =20
> 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 =20
> =20
> =20
> =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=
=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F
> igraph-help mailing list
> igraph-help=40nongnu.org (mailto:igraph-help=40nongnu.org)
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Mon Dec 02 18:39:50 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vnd5i-000136-U6
for mharc-igraph-help@gnu.org; Mon, 02 Dec 2013 18:39:50 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:45605)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnd5b-00012S-EZ
for igraph-help@nongnu.org; Mon, 02 Dec 2013 18:39:49 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vnd5V-0008PM-IX
for igraph-help@nongnu.org; Mon, 02 Dec 2013 18:39:43 -0500
Received: from mail-bk0-x22a.google.com ([2a00:1450:4008:c01::22a]:59173)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnd5V-0008PC-9n
for igraph-help@nongnu.org; Mon, 02 Dec 2013 18:39:37 -0500
Received: by mail-bk0-f42.google.com with SMTP id w11so5803662bkz.1
for ; Mon, 02 Dec 2013 15:39:36 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=date:from:to:message-id:in-reply-to:references:subject:mime-version
:content-type:content-transfer-encoding:content-disposition;
bh=1mnfrHGR7Lm2DvXqlYP+SWzOmk+JExOR1PT6nkhDgME=;
b=HB3byDn0+AV5xm2ls4OKziuMUD3CCQFuExr0UAjKHd0H9YlHW+8XjN/UIFlLR7Gqpn
A4Z56nRKJ0GjAZIKIYv2APK5Ce7l8ZrseBffO6WpM3aCLyLXxI19jMeyA/XqUfZhl4Tx
gp5IifmD83uHNOtemYbpps9cru7cg8PMSGjTgnCusS+DOjPhcGHDv+LYNJ0/vQUzkN90
hDAjb1T9myJrYaacbIPYi4sx5MfISlqHKQTQsc45KOLQerq2Oev5gyBl8RpejSvtN/Dm
zAmjcYHrlVw2bs4rUasiWSd+WClpPee+2sOb8mGlkpNJk122K4/Jh0EMa7444a72D7K1
efWw==
X-Received: by 10.205.65.81 with SMTP id xl17mr159057bkb.66.1386027576311;
Mon, 02 Dec 2013 15:39:36 -0800 (PST)
Received: from [192.168.1.3] (BC240C53.catv.pool.telekom.hu. [188.36.12.83])
by mx.google.com with ESMTPSA id l5sm31470420bko.7.2013.12.02.15.39.35
for
(version=TLSv1 cipher=RC4-SHA bits=128/128);
Mon, 02 Dec 2013 15:39:35 -0800 (PST)
Date: Tue, 3 Dec 2013 00:39:34 +0100
From: =?utf-8?Q?Tam=C3=A1s_Nepusz?=
To: Help for igraph users
Message-ID:
In-Reply-To:
References:
X-Mailer: sparrow 1.6.4 (build 1178)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2a00:1450:4008:c01::22a
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 02 Dec 2013 23:39:49 -0000
Hi Matthew, =20
So, the whole story is as follows. igraph uses ARPACK to find the dominan=
t eigenvalue of the A*A=E2=80=99 and A=E2=80=99*A matrices (where A is th=
e adjacency matrix) and the corresponding eigenvectors in order to obtain=
the hub and authority scores. This works fine in most cases - however, i=
n your case, igraph fails because the dominant eigenvalue (4 in your case=
) has two corresponding eigenvectors, one of which is the one you see and=
the other is the one you would expect intuitively. =46or what it=E2=80=99=
s worth, here are the two eigenvectors (normalized conveniently):
v1 =3D =5B1 0 0 0 0 0 0=5D
v2 =3D =5B0 2 1 0 1 0 0=5D
It is easy to confirm that both are valid eigenvectors, and it is also ea=
sy to confirm that both satisfy the HITS equations. Suppose you start out=
from v1 as the hub scores. The authority score of each vertex is then th=
e sum of the hub scores of its predecessors, so we get:
w1 =3D =5B0 1 1 0 1 1 0=5D
since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is the only=
node with a nonzero hub score. Now, let us calculate the hub scores agai=
n from the authority scores we have obtained above. In order to do that, =
we have to take the sum of the authority scores of the successors for eac=
h node. The result is:
v1=E2=80=99 =3D =5B4 0 0 0 0 0 0=5D
This is indeed 4 times v1, so v1 is an eigenvector of A*A=E2=80=99 with a=
corresponding eigenvalue of 4. In other words, igraph is not =E2=80=9Cwr=
ong=E2=80=9D, it is just that your graph has a structure for which the hu=
b and authority scores are not well-defined.
-- =20
T.
On Monday, 2 December 2013 at 23:15, Tam=C3=A1s Nepusz wrote:
> Hi Matthew, =20
> =20
> Yes, that=E2=80=99s odd indeed. Let me double-check our code; I suspect=
an ARPACK convergence problem here but I=E2=80=99m not sure (and I don=E2=
=80=99t know why there=E2=80=99s no warning if ARPACK indeed fails to con=
verge). =20
> =20
> -- =20
> T.
> =20
> =20
> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
> =20
> > I am considering this small directed graph. =20
> > =20
> > The results score node 1 as the dominate hub and the rest of the node=
s with value 0 (i.e., no' hubness'). This seems odd to me. =46or example,=
node 2, has outlinks to 3 different nodes (1,4, and 7). So, I would expe=
ct it to have some relative level of hubness. =20
> > =20
> > > g <- graph.empty() =20
> > > g <- g+vertices(1,2,3,4,5,6,7)
> > > g <- g+edge(=221=22,=222=22)
> > > g <- g+edge(=221=22,=223=22)
> > > g <- g+edge(=221=22,=225=22)
> > > g <- g+edge(=221=22,=226=22)
> > > g <- g+edge(=222=22,=221=22)
> > > g <- g+edge(=222=22,=224=22)
> > > g <- g+edge(=223=22,=221=22)
> > > g <- g+edge(=225=22,=221=22)
> > > g <- g+edge(=222=22,=227=22)
> > > E(g)
> > =20
> > =20
> > =20
> > Edge sequence:
> > =20
> > =5B1=5D 1 -> 2
> > =5B2=5D 1 -> 3
> > =5B3=5D 1 -> 5
> > =5B4=5D 1 -> 6
> > =5B5=5D 2 -> 1
> > =5B6=5D 2 -> 4
> > =5B7=5D 3 -> 1
> > =5B8=5D 5 -> 1
> > =5B9=5D 2 -> 7
> > =20
> > > hub.score(g,scale=3D=46ALSE)=24vector
> > =20
> > =20
> > 1 2 3 4 5 6 7 =20
> > 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000=
=20
> > =20
> > =20
> > =5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=
=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F=5F
> > igraph-help mailing list
> > igraph-help=40nongnu.org (mailto:igraph-help=40nongnu.org)
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
> =20
From MAILER-DAEMON Tue Dec 03 03:04:30 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vnky6-0007wP-9s
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 03:04:30 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:36074)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnky3-0007w1-E4
for igraph-help@nongnu.org; Tue, 03 Dec 2013 03:04:28 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vnky2-0001Yb-9k
for igraph-help@nongnu.org; Tue, 03 Dec 2013 03:04:27 -0500
Received: from mail-ob0-x244.google.com ([2607:f8b0:4003:c01::244]:36747)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnky2-0001YV-4M
for igraph-help@nongnu.org; Tue, 03 Dec 2013 03:04:26 -0500
Received: by mail-ob0-f196.google.com with SMTP id va2so3361212obc.3
for ; Tue, 03 Dec 2013 00:04:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to:content-type;
bh=kHpLyM80OLwOMm2zNuoz853OKqR4ABt06Ej3Hc++sB4=;
b=QdiRTVVtr8MtxNJ1iV7F7rjwkORtOESAB1d4HedJl03wUFmLqYHedhZmainej/0UBn
dlzsGEeB/D2yoKMNWIeFkYIvhp3WXp2bCI9ZcQdM+G0NoBGFbQGzOi53nuRwDjbmwdY6
54nkNOsOK5D1FuC3Pso+FQRqjoGSEwnV5knOSUoFlDIpFe7rCORIxVyV2Ok5A7Mc9RUQ
sGWqyktObWEL82wDboB08NDddgAQH1tqjfxSD6ExI4v4nDN+QEJ464EP7wcXJ6JQMEiz
Tog/o00uOGHdBR6SKTWEDuyA9fyABkxy0SykgR7GaD1QLHgzTf3yI4KTKHvfZ9hCo1lE
7Ryw==
MIME-Version: 1.0
X-Received: by 10.182.153.196 with SMTP id vi4mr5835obb.75.1386057864979; Tue,
03 Dec 2013 00:04:24 -0800 (PST)
Received: by 10.182.132.73 with HTTP; Tue, 3 Dec 2013 00:04:24 -0800 (PST)
Date: Tue, 3 Dec 2013 16:04:24 +0800
Message-ID:
From: lovelose
To: igraph-help@nongnu.org
Content-Type: multipart/alternative; boundary=089e015382acae4f0904ec9cbe64
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:4003:c01::244
Subject: [igraph] plot VertexClustering help
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 08:04:28 -0000
--089e015382acae4f0904ec9cbe64
Content-Type: text/plain; charset=ISO-8859-1
Hi everyone,
I have just started out with igraph in the Python interface. I want to plot
the VertexClustering which different communities are separated. I have run
the simple code below:
from igraph import *
g=Graph.Barabasi(300,5)
g1=Graph.commuity_walktrap(g)
g2=VertexDendrogram.as_clustering(g1)
plot(g2)
The problem now is that the result is different communities are mixed
together in a picture and I can't figure out single one community directly.
Is there some function can separate different communities (such as,
community1 is on the left side and community2 is on the right side) , or do
I have to redraw the network?
I have found the function cluster_graph(), but it contracts each community
into a vertex. The connections inside a community are invisible.
Thank you.
Regards,
Strong
--089e015382acae4f0904ec9cbe64
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Does anyone know if there a simi=
lar method to=A0Blissigraph_canonical_permutation() in the python library?<=
/div>

--047d7bdc8b5e1fd60504ec92e6b1--
From MAILER-DAEMON Mon Dec 02 15:24:54 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vna34-0007eG-BE
for mharc-igraph-help@gnu.org; Mon, 02 Dec 2013 15:24:54 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:33598)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from Thanks

=A0 =A0 - Frank

I am considering this small directe= d graph.=A0

The re= sults score node 1 as the dominate hub and the rest of the nodes with value= 0 (i.e., no' hubness'). This seems odd to me. For example, node 2,= has outlinks to 3 different nodes (1,4, and 7). So, I would expect it to h= ave some relative level of hubness.

> g <- graph.em= pty()

> g <- g+vertices(1,2,3,4,5,6,7)

> g <- g+edge("1","2")

> g <- g+edge("1","3")

> g <- g+edge("1","5")

> g <- g+edge("1","6")

> g <- g+edge("2","1")

> g <- g+edge("2","4")

> g <- g+edge("3","1")

> g <- g+edge("5","1")

=> g <- g+edge("2","7")

> E(g)

Edge sequence:

=A0=A0=A0=A0=A0=A0=A0=A0=A0

[1] 1 -> 2

[2] 1 -> 3

[3] 1 -> 5

[4] 1 -> 6

[5] 2 -> 1

[6] 2 -> 4

[7] 3 -> 1

[8] 5 -> 1

[9] 2 -> =
7

=A0

> hub.score(g,scale=3DFALSE)$vector

=A0 =A0 =A0 =A0 1 =A0 =A0 =A0 =A0 2 =A0 =A0 =A0 =A0 3 =A0 = =A0 =A0 =A0 4 =A0 =A0 =A0 =A0 5 =A0 =A0 =A0 =A0 6 =A0 =A0 =A0 =A0 7=A0

<= p class=3D"MsoNormal">0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0= 000000 0.0000000=A0Hi everyone,

) id 1VnmlQ-00074x-Lh
for igraph-help@nongnu.org; Tue, 03 Dec 2013 04:59:39 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1VnmlK-0004oH-F9
for igraph-help@nongnu.org; Tue, 03 Dec 2013 04:59:32 -0500
Received: from mout.web.de ([212.227.15.14]:53541)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnmlK-0004nw-5o
for igraph-help@nongnu.org; Tue, 03 Dec 2013 04:59:26 -0500
Received: from [192.168.178.45] ([77.182.111.205]) by smtp.web.de (mrweb103)
with ESMTPSA (Nemesis) id 0Mb8sh-1W3W3k3bFj-00Kgni for
; Tue, 03 Dec 2013 10:59:23 +0100
Message-ID: <529DAB7B.2050107@web.de>
Date: Tue, 03 Dec 2013 10:59:23 +0100
From: Frederik Elwert
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.1.1
MIME-Version: 1.0
To: igraph-help@nongnu.org
References:
In-Reply-To:
X-Enigmail-Version: 1.5.2
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
X-Provags-ID: V03:K0:hJImcwkWHYukZMSwuEv5hR4wTe9k3anhjAuhw9M2Jh1pjTlSLkx
3HFiwc+pi+mKKUneVR9B1pj3lPbk18GdBEbbK3ch2q+GbziP5pNqGX8jcamAx/+QTU/82K4
KhX3Gp9iF1D/nu3YfaUsT1dHiozz/Y9gaJQkXxBBB6qlB/u+llf1H21QPksP4K/AYTorSMM
GYI8iLFjwBolzOXKHERUw==
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic]
X-Received-From: 212.227.15.14
Subject: Re: [igraph] plot VertexClustering help
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 09:59:39 -0000
Hello Strong,
if I understood you correctly, you want to have a graph layout that
separates your clusters more visibly?
I did this by calculating a two-level layout: I first calculated the
layout of the contracted community graph in order to find a place for
each community, and then I calculated the layout for the original graph
in a way that places each community according to the first layout.
In my case, g1 is the contracted graph, while g2 is the original graph.
This is my solution in R, but it should be doable in Python along
similar lines:
# Layout for community graph
outer.layout <- layout.auto(g1) * vcount(g1)
# Create empty layout for orignal graph
inner.layout <- matrix(nrow=vcount(g2), ncol=2)
r <- 2.9
for (comm in 1:length(contracted.community)) {
# IDs of community members in outer graph
vids <- which(membership(contracted.community) == comm)
# calculate layout for community
comm.graph <- induced.subgraph(g2, vids)
comm.layout <- layout.auto(comm.graph)
# normalize community layout into corresponding outer graph vertex
bbox <- outer.layout[comm,] + c(-r, -r, r, r)
comm.layout <- layout.norm(comm.layout, xmin=bbox[1], ymin=bbox[2],
xmax=bbox[3], ymax=bbox[4])
inner.layout[vids,] <- comm.layout
}
plot(contracted.community, g2, layout=inner.layout,
edge.color=c("black", "gray")[crossing(contracted.community,
g2)+1])
Frederik
Am 03.12.2013 09:04, schrieb lovelose:
> Hi everyone,
> I have just started out with igraph in the Python interface. I want to
> plot the VertexClustering which different communities are separated. I
> have run the simple code below:
>
> from igraph import *
> g=Graph.Barabasi(300,5)
> g1=Graph.commuity_walktrap(g)
> g2=VertexDendrogram.as_clustering(g1)
> plot(g2)
>
> The problem now is that the result is different communities are mixed
> together in a picture and I can't figure out single one community directly.
>
> Is there some function can separate different communities (such as,
> community1 is on the left side and community2 is on the right side) , or
> do I have to redraw the network?
> I have found the function cluster_graph(), but it contracts each
> community into a vertex. The connections inside a community are invisible.
> Thank you.
>
> Regards,
> Strong
>
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
From MAILER-DAEMON Tue Dec 03 06:58:30 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1VnocY-0000wB-Sw
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 06:58:30 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:34585)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnocR-0000mY-Jp
for igraph-help@nongnu.org; Tue, 03 Dec 2013 06:58:29 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1VnocG-0001l4-T7
for igraph-help@nongnu.org; Tue, 03 Dec 2013 06:58:23 -0500
Received: from mail-qa0-x234.google.com ([2607:f8b0:400d:c00::234]:39434)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnocG-0001ky-Lx
for igraph-help@nongnu.org; Tue, 03 Dec 2013 06:58:12 -0500
Received: by mail-qa0-f52.google.com with SMTP id k4so5507962qaq.4
for ; Tue, 03 Dec 2013 03:58:12 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=references:mime-version:in-reply-to:content-type
:content-transfer-encoding:message-id:cc:from:subject:date:to;
bh=IFSmc3/nqKB7irlJJNIyFS2Q6OihpZ7E5afqzWheHQQ=;
b=lpDRAep30zLFy1Jl5JtXEFqxWer5kgtco/vN0gMStcPAoWbs2YIfOFcIyN5nU3KHsP
kTwlf+q14o16L8tN0Pw3eOhwsMadmnjlxANM99TQ0GUQhhm17h5FO+tja+DBlbddPGeM
3Tw/AHMMd0FI8IeFjCjTnGCdgVwolrrouUl8lsc1J7KeuBf7bsWPRr6ksyw6FPhF8Lk6
SwMQ1GpwTLB93ajKSwL+P4m3GuPEUHJPYOjj6iHHHyOn7wC1r6XEIUS91PURnimZuW9o
YXiGi2ihQ4SgGD/xDZoacZn9MuVWgg6gAUOMndhyxIs5F57EG/C0+vK6425qYAK6i9uY
w2MQ==
X-Received: by 10.49.52.34 with SMTP id q2mr96497403qeo.10.1386071892099;
Tue, 03 Dec 2013 03:58:12 -0800 (PST)
Received: from [192.168.1.4] (pool-96-245-53-218.phlapa.fios.verizon.net.
[96.245.53.218]) by mx.google.com with ESMTPSA id
x10sm135120873qas.5.2013.12.03.03.58.11 for
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Tue, 03 Dec 2013 03:58:11 -0800 (PST)
References:
Mime-Version: 1.0 (1.0)
In-Reply-To:
Content-Type: text/plain;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
Message-Id: <0A7FAFC9-985E-46D7-BD0C-78357BEB9DE0@gmail.com>
Cc: Help for igraph users
X-Mailer: iPhone Mail (11B554a)
From: Matthew Galati
Date: Tue, 3 Dec 2013 06:58:08 -0500
To: Help for igraph users
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:400d:c00::234
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 11:58:29 -0000
Yes. I have even reading up on this topic. I think the hub/auth scores assum=
e a unique dominant eigenvalue - which is not true on this case (and many ot=
hers I have seen). I am trying to see if anything can be done. I think that,=
by adding epsilon to all matrix coefficients, this will ensure that the eig=
envalue is unique. This idea does lead to sensible results in the cases I ha=
ve looked at. It forces the matrix to be positive, which implies a unique do=
minant eigenvalue. Unfortunately, this makes A fully dense - so, I am hoping=
there is a better way.=20
Sent from my iPhone
> On Dec 2, 2013, at 6:39 PM, Tam=C3=A1s Nepusz wrote:
>=20
> Hi Matthew, =20
>=20
> So, the whole story is as follows. igraph uses ARPACK to find the dominant=
eigenvalue of the A*A=E2=80=99 and A=E2=80=99*A matrices (where A is the ad=
jacency matrix) and the corresponding eigenvectors in order to obtain the hu=
b and authority scores. This works fine in most cases - however, in your cas=
e, igraph fails because the dominant eigenvalue (4 in your case) has two cor=
responding eigenvectors, one of which is the one you see and the other is th=
e one you would expect intuitively. For what it=E2=80=99s worth, here are th=
e two eigenvectors (normalized conveniently):
>=20
> v1 =3D [1 0 0 0 0 0 0]
> v2 =3D [0 2 1 0 1 0 0]
>=20
> It is easy to confirm that both are valid eigenvectors, and it is also eas=
y to confirm that both satisfy the HITS equations. Suppose you start out fro=
m v1 as the hub scores. The authority score of each vertex is then the sum o=
f the hub scores of its predecessors, so we get:
>=20
> w1 =3D [0 1 1 0 1 1 0]
>=20
> since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is the only n=
ode with a nonzero hub score. Now, let us calculate the hub scores again fro=
m the authority scores we have obtained above. In order to do that, we have t=
o take the sum of the authority scores of the successors for each node. The r=
esult is:
>=20
> v1=E2=80=99 =3D [4 0 0 0 0 0 0]
>=20
> This is indeed 4 times v1, so v1 is an eigenvector of A*A=E2=80=99 with a c=
orresponding eigenvalue of 4. In other words, igraph is not =E2=80=9Cwrong=E2=
=80=9D, it is just that your graph has a structure for which the hub and aut=
hority scores are not well-defined.
>=20
> -- =20
> T.
>=20
>=20
>> On Monday, 2 December 2013 at 23:15, Tam=C3=A1s Nepusz wrote:
>>=20
>> Hi Matthew, =20
>>=20
>> Yes, that=E2=80=99s odd indeed. Let me double-check our code; I suspect a=
n ARPACK convergence problem here but I=E2=80=99m not sure (and I don=E2=80=99=
t know why there=E2=80=99s no warning if ARPACK indeed fails to converge). =20=
>>=20
>> -- =20
>> T.
>>=20
>>=20
>>> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
>>>=20
>>> I am considering this small directed graph. =20
>>>=20
>>> The results score node 1 as the dominate hub and the rest of the nodes w=
ith value 0 (i.e., no' hubness'). This seems odd to me. For example, node 2,=
has outlinks to 3 different nodes (1,4, and 7). So, I would expect it to ha=
ve some relative level of hubness. =20
>>>=20
>>>> g <- graph.empty() =20
>>>> g <- g+vertices(1,2,3,4,5,6,7)
>>>> g <- g+edge("1","2")
>>>> g <- g+edge("1","3")
>>>> g <- g+edge("1","5")
>>>> g <- g+edge("1","6")
>>>> g <- g+edge("2","1")
>>>> g <- g+edge("2","4")
>>>> g <- g+edge("3","1")
>>>> g <- g+edge("5","1")
>>>> g <- g+edge("2","7")
>>>> E(g)
>>>=20
>>>=20
>>>=20
>>> Edge sequence:
>>>=20
>>> [1] 1 -> 2
>>> [2] 1 -> 3
>>> [3] 1 -> 5
>>> [4] 1 -> 6
>>> [5] 2 -> 1
>>> [6] 2 -> 4
>>> [7] 3 -> 1
>>> [8] 5 -> 1
>>> [9] 2 -> 7
>>>=20
>>>> hub.score(g,scale=3DFALSE)$vector
>>>=20
>>>=20
>>> 1 2 3 4 5 6 7 =20
>>> 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 =20=
>>>=20
>>>=20
>>> _______________________________________________
>>> igraph-help mailing list
>>> igraph-help@nongnu.org (mailto:igraph-help@nongnu.org)
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>=20
>=20
>=20
>=20
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Tue Dec 03 07:09:21 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vnon3-0001Qm-0e
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 07:09:21 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:38433)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnomw-0001LR-EJ
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:09:19 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Vnomu-0006LV-8v
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:09:14 -0500
Received: from mail-qa0-x234.google.com ([2607:f8b0:400d:c00::234]:53180)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Vnomu-0006LE-3d
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:09:12 -0500
Received: by mail-qa0-f52.google.com with SMTP id k4so5529911qaq.11
for ; Tue, 03 Dec 2013 04:09:11 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-type:content-transfer-encoding;
bh=4BhxqLgSCFd+A9emFwEsJ6Pp0Jk+5pHmBHvU16dlCe4=;
b=AvQQzny1xursWz41q4bKV8RlsXZ/zp/K2qBXpgvflNasayIBbsrMHLhEmch0Nm5ncV
oG+h+7osfYS99sK4MWwYJ6O9HWZSKptNY19ZsGPbzwJdSGVhHH5AqhB1oo0sA43oBnTe
0jnN2mc8bMytty8tSa9KY2w6mP8skkNPowmFSn+F2evtLMfzWTu9NVzQYcsyLH4Aei0H
gGYgH+oP1baLDT/o3Z6ah2+k1uYlFjB6m12PRJdEGrNu4Hjaz3L0NvRsaToo6m+gKbJp
kDHbLIu86TSyWsW2ckmzJ231njZAiHO6ccPpoGSnkNHJTPqzMZbyQJEKxdwnoOfYiblq
yKmQ==
MIME-Version: 1.0
X-Received: by 10.224.80.129 with SMTP id t1mr83890470qak.95.1386072551508;
Tue, 03 Dec 2013 04:09:11 -0800 (PST)
Received: by 10.140.51.199 with HTTP; Tue, 3 Dec 2013 04:09:11 -0800 (PST)
In-Reply-To: <0A7FAFC9-985E-46D7-BD0C-78357BEB9DE0@gmail.com>
References:
<0A7FAFC9-985E-46D7-BD0C-78357BEB9DE0@gmail.com>
Date: Tue, 3 Dec 2013 07:09:11 -0500
Message-ID:
From: =?ISO-8859-1?B?R+Fib3IgQ3PhcmRp?=
To: Help for igraph users
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:400d:c00::234
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 12:09:19 -0000
A dense matrix is not necessarily a problem. All we need is that the
matrix-matrix product and matrix-vector product operations are easy,
which holds if your matrix is sparse + constant.
However, I don't think this would work in practice. Yes, in theory the
eigenvalue is positive and unique, but in practice, if epsilon is
small, then the top two eigenvalues will be close, causing numerical
instabilities.
(I must admit, I had no time to follow through Tamas's argument, so
fixme. Thanks.)
Gabor
On Tue, Dec 3, 2013 at 6:58 AM, Matthew Galati w=
rote:
> Yes. I have even reading up on this topic. I think the hub/auth scores as=
sume a unique dominant eigenvalue - which is not true on this case (and man=
y others I have seen). I am trying to see if anything can be done. I think =
that, by adding epsilon to all matrix coefficients, this will ensure that t=
he eigenvalue is unique. This idea does lead to sensible results in the cas=
es I have looked at. It forces the matrix to be positive, which implies a u=
nique dominant eigenvalue. Unfortunately, this makes A fully dense - so, I =
am hoping there is a better way.
>
> Sent from my iPhone
>
>> On Dec 2, 2013, at 6:39 PM, Tam=E1s Nepusz wrote:
>>
>> Hi Matthew,
>>
>> So, the whole story is as follows. igraph uses ARPACK to find the domina=
nt eigenvalue of the A*A=92 and A=92*A matrices (where A is the adjacency m=
atrix) and the corresponding eigenvectors in order to obtain the hub and au=
thority scores. This works fine in most cases - however, in your case, igra=
ph fails because the dominant eigenvalue (4 in your case) has two correspon=
ding eigenvectors, one of which is the one you see and the other is the one=
you would expect intuitively. For what it=92s worth, here are the two eige=
nvectors (normalized conveniently):
>>
>> v1 =3D [1 0 0 0 0 0 0]
>> v2 =3D [0 2 1 0 1 0 0]
>>
>> It is easy to confirm that both are valid eigenvectors, and it is also e=
asy to confirm that both satisfy the HITS equations. Suppose you start out =
from v1 as the hub scores. The authority score of each vertex is then the s=
um of the hub scores of its predecessors, so we get:
>>
>> w1 =3D [0 1 1 0 1 1 0]
>>
>> since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is the onl=
y node with a nonzero hub score. Now, let us calculate the hub scores again=
from the authority scores we have obtained above. In order to do that, we =
have to take the sum of the authority scores of the successors for each nod=
e. The result is:
>>
>> v1=92 =3D [4 0 0 0 0 0 0]
>>
>> This is indeed 4 times v1, so v1 is an eigenvector of A*A=92 with a corr=
esponding eigenvalue of 4. In other words, igraph is not =93wrong=94, it is=
just that your graph has a structure for which the hub and authority score=
s are not well-defined.
>>
>> --
>> T.
>>
>>
>>> On Monday, 2 December 2013 at 23:15, Tam=E1s Nepusz wrote:
>>>
>>> Hi Matthew,
>>>
>>> Yes, that=92s odd indeed. Let me double-check our code; I suspect an AR=
PACK convergence problem here but I=92m not sure (and I don=92t know why th=
ere=92s no warning if ARPACK indeed fails to converge).
>>>
>>> --
>>> T.
>>>
>>>
>>>> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
>>>>
>>>> I am considering this small directed graph.
>>>>
>>>> The results score node 1 as the dominate hub and the rest of the nodes=
with value 0 (i.e., no' hubness'). This seems odd to me. For example, node=
2, has outlinks to 3 different nodes (1,4, and 7). So, I would expect it t=
o have some relative level of hubness.
>>>>
>>>>> g <- graph.empty()
>>>>> g <- g+vertices(1,2,3,4,5,6,7)
>>>>> g <- g+edge("1","2")
>>>>> g <- g+edge("1","3")
>>>>> g <- g+edge("1","5")
>>>>> g <- g+edge("1","6")
>>>>> g <- g+edge("2","1")
>>>>> g <- g+edge("2","4")
>>>>> g <- g+edge("3","1")
>>>>> g <- g+edge("5","1")
>>>>> g <- g+edge("2","7")
>>>>> E(g)
>>>>
>>>>
>>>>
>>>> Edge sequence:
>>>>
>>>> [1] 1 -> 2
>>>> [2] 1 -> 3
>>>> [3] 1 -> 5
>>>> [4] 1 -> 6
>>>> [5] 2 -> 1
>>>> [6] 2 -> 4
>>>> [7] 3 -> 1
>>>> [8] 5 -> 1
>>>> [9] 2 -> 7
>>>>
>>>>> hub.score(g,scale=3DFALSE)$vector
>>>>
>>>>
>>>> 1 2 3 4 5 6 7
>>>> 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000
>>>>
>>>>
>>>> _______________________________________________
>>>> igraph-help mailing list
>>>> igraph-help@nongnu.org (mailto:igraph-help@nongnu.org)
>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> igraph-help@nongnu.org
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Tue Dec 03 07:57:26 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1VnpXa-0000bJ-IM
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 07:57:26 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:46827)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnpXX-0000au-T7
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:57:24 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1VnpXT-0004Ez-6P
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:57:23 -0500
Received: from mail-pd0-x235.google.com ([2607:f8b0:400e:c02::235]:51334)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnpXS-0004Eh-V0
for igraph-help@nongnu.org; Tue, 03 Dec 2013 07:57:19 -0500
Received: by mail-pd0-f181.google.com with SMTP id p10so19886386pdj.40
for ; Tue, 03 Dec 2013 04:57:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to:content-type;
bh=/2jkYSicDT2+m+jc5vWyXY5XoY0cN/w6ANLv8xf+E6s=;
b=LB61ER2ecOqG9hcFEkFsjgtHgalOZwntZDr3SIf+wl+5Nvlawhe0RPw1fc1TcXqmjV
sDv9ycs0jvEipAzpozl6+lJo7dl2xtGxKkiudOJMILQFziiD6UfCmFljflxNeib+gKvh
TkgvPHSDOXlk1mV/6ucpoWIHKqQmnhCBZ+OSSvRfDIotdM6quy4ddPbeYmC1JycOiqb3
yFShySCazdkT/nfpf3NYq5GzMNH9HIUkZZmm91Co97dKZtyIYn339e1tnEuUWf4+8+kz
Ly0gm7E7T4e9MN9pqTAIjIiUEXSoAtoZM8nc/7SkhrAWlWMEoyOZzLbMcJ5N1EewN3sX
xMbw==
MIME-Version: 1.0
X-Received: by 10.68.136.34 with SMTP id px2mr37836069pbb.113.1386075437201;
Tue, 03 Dec 2013 04:57:17 -0800 (PST)
Received: by 10.68.43.137 with HTTP; Tue, 3 Dec 2013 04:57:17 -0800 (PST)
Date: Tue, 3 Dec 2013 13:57:17 +0100
Message-ID:
From: Hermann Norpois
To: igraph-help
Content-Type: multipart/alternative; boundary=047d7b15a88110feff04eca0d601
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:400e:c02::235
Subject: [igraph] identify edges and edge.connectivity
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 12:57:25 -0000
--047d7b15a88110feff04eca0d601
Content-Type: text/plain; charset=ISO-8859-1
Hello,
using edge.connectivity (g) I get the minimum edge connectivity of a graph,
for instance 1. Now I would like to identify those edges in order to remove
them. Could you please give me a hint how this might work?
Thanks
Hermann
--047d7b15a88110feff04eca0d601
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Thanks

Hermann

--047d7b15a88110feff04eca0d601--
From MAILER-DAEMON Tue Dec 03 09:21:01 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1VnqqT-0006s5-DQ
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 09:21:01 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:38670)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnqqL-0006rP-VO
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:20:59 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1VnqqJ-00074Y-Lq
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:20:53 -0500
Received: from mail-oa0-x230.google.com ([2607:f8b0:4003:c02::230]:44669)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnqqJ-00074M-E0
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:20:51 -0500
Received: by mail-oa0-f48.google.com with SMTP id l6so14833653oag.21
for ; Tue, 03 Dec 2013 06:20:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-type; bh=g9tQOPx24g3d6VTbStR0DHoA23gt4HFYquXJAI32efA=;
b=h40BHhc7GeJzARUIBbMuo0MWmf1hu1zRf9W3/B5sKzvMNpYbd8kgeKO8TgupZS03MN
xeL/GLHOKeWqNb78HA+gD4T9eA4UptFHq76Ac0wR3XEPS/65KPdyHnWelYWcE2gBeHSd
z6UW/wCKXlUebN+f10fI86ClrfUMRdDSFtgMTxwlaKmqOUs4p6CAQD9v/W/E5oY/SbDU
3NyBnWFd4vHUqnkG249kn+JIA80ShlKAxbJ9R2iPEfYPGdd4ZzuD+Ghf28DIEgBsMtGe
qj0UD640dghDBa5DPg6oHVsS/V5dnS6cOUJ5r26ndLmm8WjAXnEm22myKzeMLY9Oj6ma
JkdA==
MIME-Version: 1.0
X-Received: by 10.182.215.202 with SMTP id ok10mr1304915obc.62.1386080450706;
Tue, 03 Dec 2013 06:20:50 -0800 (PST)
Received: by 10.60.44.37 with HTTP; Tue, 3 Dec 2013 06:20:50 -0800 (PST)
In-Reply-To:
References:
<0A7FAFC9-985E-46D7-BD0C-78357BEB9DE0@gmail.com>
Date: Tue, 3 Dec 2013 09:20:50 -0500
Message-ID:
From: Matthew Galati
To: Help for igraph users
Content-Type: multipart/alternative; boundary=001a11c24a52e5056404eca2009b
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:4003:c02::230
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 03 Dec 2013 14:20:59 -0000
--001a11c24a52e5056404eca2009b
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Yes. I imagine this might cause numeric instability. But, this is better
than getting results that make no sense conceptually. I suggest only doing
that if you find that the leading eigenvalue is non-unique (as a backup
plan).
On Tue, Dec 3, 2013 at 7:09 AM, G=E1bor Cs=E1rdi w=
rote:
> A dense matrix is not necessarily a problem. All we need is that the
> matrix-matrix product and matrix-vector product operations are easy,
> which holds if your matrix is sparse + constant.
>
> However, I don't think this would work in practice. Yes, in theory the
> eigenvalue is positive and unique, but in practice, if epsilon is
> small, then the top two eigenvalues will be close, causing numerical
> instabilities.
>
> (I must admit, I had no time to follow through Tamas's argument, so
> fixme. Thanks.)
>
> Gabor
>
> On Tue, Dec 3, 2013 at 6:58 AM, Matthew Galati
> wrote:
> > Yes. I have even reading up on this topic. I think the hub/auth scores
> assume a unique dominant eigenvalue - which is not true on this case (and
> many others I have seen). I am trying to see if anything can be done. I
> think that, by adding epsilon to all matrix coefficients, this will ensur=
e
> that the eigenvalue is unique. This idea does lead to sensible results in
> the cases I have looked at. It forces the matrix to be positive, which
> implies a unique dominant eigenvalue. Unfortunately, this makes A fully
> dense - so, I am hoping there is a better way.
> >
> > Sent from my iPhone
> >
> >> On Dec 2, 2013, at 6:39 PM, Tam=E1s Nepusz wrote:
> >>
> >> Hi Matthew,
> >>
> >> So, the whole story is as follows. igraph uses ARPACK to find the
> dominant eigenvalue of the A*A=92 and A=92*A matrices (where A is the adj=
acency
> matrix) and the corresponding eigenvectors in order to obtain the hub and
> authority scores. This works fine in most cases - however, in your case,
> igraph fails because the dominant eigenvalue (4 in your case) has two
> corresponding eigenvectors, one of which is the one you see and the other
> is the one you would expect intuitively. For what it=92s worth, here are =
the
> two eigenvectors (normalized conveniently):
> >>
> >> v1 =3D [1 0 0 0 0 0 0]
> >> v2 =3D [0 2 1 0 1 0 0]
> >>
> >> It is easy to confirm that both are valid eigenvectors, and it is also
> easy to confirm that both satisfy the HITS equations. Suppose you start o=
ut
> from v1 as the hub scores. The authority score of each vertex is then the
> sum of the hub scores of its predecessors, so we get:
> >>
> >> w1 =3D [0 1 1 0 1 1 0]
> >>
> >> since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is the
> only node with a nonzero hub score. Now, let us calculate the hub scores
> again from the authority scores we have obtained above. In order to do
> that, we have to take the sum of the authority scores of the successors f=
or
> each node. The result is:
> >>
> >> v1=92 =3D [4 0 0 0 0 0 0]
> >>
> >> This is indeed 4 times v1, so v1 is an eigenvector of A*A=92 with a
> corresponding eigenvalue of 4. In other words, igraph is not =93wrong=94,=
it is
> just that your graph has a structure for which the hub and authority scor=
es
> are not well-defined.
> >>
> >> --
> >> T.
> >>
> >>
> >>> On Monday, 2 December 2013 at 23:15, Tam=E1s Nepusz wrote:
> >>>
> >>> Hi Matthew,
> >>>
> >>> Yes, that=92s odd indeed. Let me double-check our code; I suspect an
> ARPACK convergence problem here but I=92m not sure (and I don=92t know wh=
y
> there=92s no warning if ARPACK indeed fails to converge).
> >>>
> >>> --
> >>> T.
> >>>
> >>>
> >>>> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
> >>>>
> >>>> I am considering this small directed graph.
> >>>>
> >>>> The results score node 1 as the dominate hub and the rest of the
> nodes with value 0 (i.e., no' hubness'). This seems odd to me. For exampl=
e,
> node 2, has outlinks to 3 different nodes (1,4, and 7). So, I would expec=
t
> it to have some relative level of hubness.
> >>>>
> >>>>> g <- graph.empty()
> >>>>> g <- g+vertices(1,2,3,4,5,6,7)
> >>>>> g <- g+edge("1","2")
> >>>>> g <- g+edge("1","3")
> >>>>> g <- g+edge("1","5")
> >>>>> g <- g+edge("1","6")
> >>>>> g <- g+edge("2","1")
> >>>>> g <- g+edge("2","4")
> >>>>> g <- g+edge("3","1")
> >>>>> g <- g+edge("5","1")
> >>>>> g <- g+edge("2","7")
> >>>>> E(g)
> >>>>
> >>>>
> >>>>
> >>>> Edge sequence:
> >>>>
> >>>> [1] 1 -> 2
> >>>> [2] 1 -> 3
> >>>> [3] 1 -> 5
> >>>> [4] 1 -> 6
> >>>> [5] 2 -> 1
> >>>> [6] 2 -> 4
> >>>> [7] 3 -> 1
> >>>> [8] 5 -> 1
> >>>> [9] 2 -> 7
> >>>>
> >>>>> hub.score(g,scale=3DFALSE)$vector
> >>>>
> >>>>
> >>>> 1 2 3 4 5 6 7
> >>>> 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.000000=
0
> >>>>
> >>>>
> >>>> _______________________________________________
> >>>> igraph-help mailing list
> >>>> igraph-help@nongnu.org (mailto:igraph-help@nongnu.org)
> >>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >>
> >>
> >>
> >>
> >> _______________________________________________
> >> igraph-help mailing list
> >> igraph-help@nongnu.org
> >> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >
> > _______________________________________________
> > igraph-help mailing list
> > igraph-help@nongnu.org
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
--001a11c24a52e5056404eca2009b
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

--001a11c24a52e5056404eca2009b--
From MAILER-DAEMON Tue Dec 03 09:29:26 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1Vnqyc-00049e-Mq
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 09:29:26 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:40847)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnqyZ-000494-Gi
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:29:25 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1VnqyU-0001h6-BS
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:29:23 -0500
Received: from mail-qa0-x229.google.com ([2607:f8b0:400d:c00::229]:52550)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1VnqyU-0001gw-6J
for igraph-help@nongnu.org; Tue, 03 Dec 2013 09:29:18 -0500
Received: by mail-qa0-f41.google.com with SMTP id j5so5628103qaq.0
for ; Tue, 03 Dec 2013 06:29:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-type:content-transfer-encoding;
bh=3AGs4y+uZI/TTwGn8+qCwSqC1no7j+PVsazFJaKySJk=;
b=WReXqtQmPFeI1bdiqeCsWw34afBrufVMg8BRQlKfvD3EdfqEDXiwr8R2SILe3OB2M1
wv6ccgpMKynDyABvYBFaeyPp6sepSR2KrM1cDELDxVm/06roZoqy0OBFzTNQtiQkKU6g
4wJwCIZUMo+Jh1NGA6UWIN+OI1qqjxcZbrHyIIlxZ69DEwVlhhRDlhjBHC/q8hh9kk1H
EwQFJbXE1nIk6wfeLByKL/p8C+/Qow253nk4BGRpf3/KBN+g4vCrJebdXWTdI6ZvFU0L
Rt0prYfNs14wVRkEx6QbdEhc5k3y4BSg67B3YvF9K8bwmGNQRO24GLPqfF61M16Bur0e
k15A==
MIME-Version: 1.0
X-Received: by 10.224.165.133 with SMTP id i5mr127048243qay.11.1386080957683;
Tue, 03 Dec 2013 06:29:17 -0800 (PST)
Received: by 10.140.51.199 with HTTP; Tue, 3 Dec 2013 06:29:17 -0800 (PST)
In-Reply-To:
References:
<0A7FAFC9-985E-46D7-BD0C-78357BEB9DE0@gmail.com>
Date: Tue, 3 Dec 2013 09:29:17 -0500
Message-ID:
From: =?ISO-8859-1?B?R+Fib3IgQ3PhcmRp?=
To: Help for igraph users
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
(bad octet value).
X-Received-From: 2607:f8b0:400d:c00::229
Subject: Re: [igraph] interpretation of hub/auth scores
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe:

I have just started out with igraph in th=
e Python interface. I want to plot the VertexClustering which different com=
munities are separated. I have run the simple code below:

=A0 =A0=
=A0=A0

=A0 =A0 =A0 from igraph import *

=A0 =A0 =A0 g=3DGraph.Barab=
asi(300,5)

=A0 =A0 =A0 g1=3DGraph.commuity_walktrap(g)

=
=A0 =A0 =A0 g2=3DVertexDendrogram.as_clustering(g1)

=A0 =A0 =A0 p=
lot(g2)

The problem now is that the result is different communities are mixed toget=
her in a picture and I can't figure out single one community directly.=
=A0

Is there some function can separate different =
communities (such as, community1 is on the left side and community2 is on t=
he right side) , or do I have to redraw the network?

I have found the function cluster_graph(), but it contracts each commu=
nity into a vertex. The connections inside a community are =A0invisible.

--089e015382acae4f0904ec9cbe64--
From MAILER-DAEMON Tue Dec 03 04:59:41 2013
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1VnmlZ-00077B-C7
for mharc-igraph-help@gnu.org; Tue, 03 Dec 2013 04:59:41 -0500
Received: from eggs.gnu.org ([2001:4830:134:3::10]:33500)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from Thank you.

Regards,

Strong

Hello,

using edge.connectivity=
(g) I get the minimum edge connectivity of a graph, for instance 1. Now I =
would like to identify those edges in order to remove them. Could you pleas=
e give me a hint how this might work?Yes. I imagine this might cause numeric instability. But, =
this is better than getting results that make no sense conceptually. I sugg=
est only doing that if you find that the leading eigenvalue is non-unique (=
as a backup plan).

On Tue, Dec 3=
, 2013 at 7:09 AM, G=E1bor Cs=E1rdi <csardi.gabor@gmail.com> wrote:

A dense matrix is not necessarily a problem.= All we need is that the

matrix-matrix product and matrix-vector product operations are easy,

which holds if your matrix is sparse + constant.

However, I don't think this would work in practice. Yes, in theory the<= br> eigenvalue is positive and unique, but in practice, if epsilon is

small, then the top two eigenvalues will be close, causing numerical

instabilities.

(I must admit, I had no time to follow through Tamas's argument, so

fixme. Thanks.)

Gabor

On Tue, Dec 3, 2013 at 6:58 AM, Matthew Galati <matthew.galati@gmail.com> wrote:

> Yes. I have even reading up on this topic. I think the hub/auth scores= assume a unique dominant eigenvalue - which is not true on this case (and = many others I have seen). I am trying to see if anything can be done. I thi= nk that, by adding epsilon to all matrix coefficients, this will ensure tha= t the eigenvalue is unique. This idea does lead to sensible results in the = cases I have looked at. It forces the matrix to be positive, which implies = a unique dominant eigenvalue. Unfortunately, this makes A fully dense - so,= I am hoping there is a better way.

>

> Sent from my iPhone

>

>> On Dec 2, 2013, at 6:39 PM, Tam=E1s Nepusz <ntamas@gmail.com> wrote:

>>

>> Hi Matthew,

>>

>> So, the whole story is as follows. igraph uses ARPACK to find the = dominant eigenvalue of the A*A=92 and A=92*A matrices (where A is the adjac= ency matrix) and the corresponding eigenvectors in order to obtain the hub = and authority scores. This works fine in most cases - however, in your case= , igraph fails because the dominant eigenvalue (4 in your case) has two cor= responding eigenvectors, one of which is the one you see and the other is t= he one you would expect intuitively. For what it=92s worth, here are the tw= o eigenvectors (normalized conveniently):

>>

>> v1 =3D [1 0 0 0 0 0 0]

>> v2 =3D [0 2 1 0 1 0 0]

>>

>> It is easy to confirm that both are valid eigenvectors, and it is = also easy to confirm that both satisfy the HITS equations. Suppose you star= t out from v1 as the hub scores. The authority score of each vertex is then= the sum of the hub scores of its predecessors, so we get:

>>

>> w1 =3D [0 1 1 0 1 1 0]

>>

>> since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is t= he only node with a nonzero hub score. Now, let us calculate the hub scores= again from the authority scores we have obtained above. In order to do tha= t, we have to take the sum of the authority scores of the successors for ea= ch node. The result is:

>>

>> v1=92 =3D [4 0 0 0 0 0 0]

>>

>> This is indeed 4 times v1, so v1 is an eigenvector of A*A=92 with = a corresponding eigenvalue of 4. In other words, igraph is not =93wrong=94,= it is just that your graph has a structure for which the hub and authority= scores are not well-defined.

>>

>> --

>> T.

>>

>>

>>> On Monday, 2 December 2013 at 23:15, Tam=E1s Nepusz wrote:

>>>

>>> Hi Matthew,

>>>

>>> Yes, that=92s odd indeed. Let me double-check our code; I susp= ect an ARPACK convergence problem here but I=92m not sure (and I don=92t kn= ow why there=92s no warning if ARPACK indeed fails to converge).

>>>

>>> --

>>> T.

>>>

>>>

>>>> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:=

>>>>

>>>> I am considering this small directed graph.

>>>>

>>>> The results score node 1 as the dominate hub and the rest = of the nodes with value 0 (i.e., no' hubness'). This seems odd to m= e. For example, node 2, has outlinks to 3 different nodes (1,4, and 7). So,= I would expect it to have some relative level of hubness.

>>>>

>>>>> g <- graph.empty()

>>>>> g <- g+vertices(1,2,3,4,5,6,7)

>>>>> g <- g+edge("1","2")

>>>>> g <- g+edge("1","3")

>>>>> g <- g+edge("1","5")

>>>>> g <- g+edge("1","6")

>>>>> g <- g+edge("2","1")

>>>>> g <- g+edge("2","4")

>>>>> g <- g+edge("3","1")

>>>>> g <- g+edge("5","1")

>>>>> g <- g+edge("2","7")

>>>>> E(g)

>>>>

>>>>

>>>>

>>>> Edge sequence:

>>>>

>>>> [1] 1 -> 2

>>>> [2] 1 -> 3

>>>> [3] 1 -> 5

>>>> [4] 1 -> 6

>>>> [5] 2 -> 1

>>>> [6] 2 -> 4

>>>> [7] 3 -> 1

>>>> [8] 5 -> 1

>>>> [9] 2 -> 7

>>>>

>>>>> hub.score(g,scale=3DFALSE)$vector

>>>>

>>>>

>>>> 1 2 3 4 5 6 7

>>>> 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.000000= 0 0.0000000

>>>>

>>>>

>>>> _______________________________________________

>>>> igraph-help mailing list

>>>> igraph-help@nong= nu.org (mailto:igraph-help@no= ngnu.org)

>>>> https://lists.nongnu.org/mailman/listinfo/igraph-= help

>>

>>

>>

>>

>> _______________________________________________

>> igraph-help mailing list

>> igraph-help@nongnu.org

>> https://lists.nongnu.org/mailman/listinfo/igraph-help=

>

> _______________________________________________

> igraph-help mailing list

> igraph-help@nongnu.org> https://lists.nongnu.org/mailman/listinfo/igraph-help

_______________________________________________

igraph-help mailing list

igraph-help@nongnu.org

https://lists.nongnu.org/mailman/listinfo/igraph-help